1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
|
constexpr ll INF = 0x1FFF'FFFF'FFFF'FFFF;//THIS CODE IS WIP
bool left(pt p) {return real(p) < 0 ||
(real(p) == 0 && imag(p) < 0);}
struct hp {
pt from, to;
hp(pt a, pt b) : from(a), to(b) {}
hp(pt dummy) : hp(dummy, dummy) {}
bool dummy() const {return from == to;}
pt dir() const {return dummy() ? to : to - from;}
bool operator<(const hp& o) const {
if (left(dir()) != left(o.dir()))
return left(dir()) > left(o.dir());
return cross(dir(), o.dir()) > 0;
}
using lll = __int128;
using ptl = complex<lll>;
ptl mul(lll m, ptl p) const {return m*p;}//ensure 128bit
bool check(const hp& a, const hp& b) const {
if (dummy() || b.dummy()) return false;
if (a.dummy()) {
ll ort = sgn(cross(b.dir(), dir()));
if (ort == 0) return cross(from, to, a.from) < 0;
return cross(b.dir(), a.dir()) * ort > 0;
}
ll y = cross(a.dir(), b.dir());
ll z = cross(b.from - a.from, b.dir());
ptl i = mul(y, a.from) + mul(z, a.dir()); //intersect a and b
// check if i is outside/right of x
return imag(conj(mul(sgn(y),dir()))*(i-mul(y,from))) < 0;
}
};
constexpr ll lim = 2e9+7;
deque<hp> intersect(vector<hp> hps) {
hps.push_back(hp(pt{lim+1,-1}));
hps.push_back(hp(pt{lim+1,1}));
sort(all(hps));
deque<hp> dq = {hp(pt{-lim, 1})};
for (auto x : hps) {
while (sz(dq) > 1 && x.check(dq.end()[-1], dq.end()[-2]))
dq.pop_back();
while (sz(dq) > 1 && x.check(dq[0], dq[1]))
dq.pop_front();
if (cross(x.dir(), dq.back().dir()) == 0) {
if (dot(x.dir(), dq.back().dir()) < 0) return {};
if (cross(x.from, x.to, dq.back().from) < 0)
dq.pop_back();
else continue;
}
dq.push_back(x);
}
while (sz(dq) > 2 && dq[0].check(dq.end()[-1], dq.end()[-2]))
dq.pop_back();
while (sz(dq) > 2 && dq.end()[-1].check(dq[0], dq[1]))
dq.pop_front();
if (sz(dq) < 3) return {};
return dq;
}
|
