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
69
70
71
| #include <iostream>
#include <queue>
using namespace std;
struct line {
pair<int, int> a, b;
};
struct sq {
line lines[4];
};
int ans, n, a, b, c, d;
queue<sq> all, g;
sq s, tmp;
int ccw(pair<int, int> a, pair<int, int> b, pair<int, int> c) {
int op = a.first * b.second + b.first * c.second + c.first * a.second -
(a.second * b.first + b.second * c.first + c.second * a.first);
return op > 0 ? 1 : !op ? 0 : -1;
}
bool isIntersect(line l1, line l2) {
if (l1.a == l2.a || l1.a == l2.b || l1.b == l2.a || l1.b == l2.b)
return true;
int ab = ccw(l1.a, l1.b, l2.a) * ccw(l1.a, l1.b, l2.b);
int cd = ccw(l2.a, l2.b, l1.a) * ccw(l2.a, l2.b, l1.b);
if (!ab && !cd) {
if (l1.a > l1.b) swap(l1.a, l1.b);
if (l2.a > l2.b) swap(l2.a, l2.b);
return l2.a <= l1.b && l1.a <= l2.b;
}
return ab <= 0 && cd <= 0;
}
bool cross(sq a, sq b) {
for (int i = 0; i < 4; i++)
for (int j = 0; j < 4; j++)
if (isIntersect(a.lines[i], b.lines[j]))
return true;
return false;
}
bool isIncludeZero(line l) {
if(l.a.second == 0 && l.b.second == 0 && l.a.first <= 0 && l.b.first >= 0) return true;
return l.a.first == 0 && l.b.first == 0 && l.a.second <= 0 && l.b.second >= 0;
}
int main() {
scanf("%d", &n);
while (n--) {
scanf("%d %d %d %d", &a, &b, &c, &d);
s.lines[0].a.first = s.lines[0].b.first = s.lines[1].a.first = s.lines[3].a.first = a;
s.lines[0].a.second = s.lines[1].a.second = s.lines[1].b.second = s.lines[2].a.second = b;
s.lines[0].b.second = s.lines[2].b.second = s.lines[3].a.second = s.lines[3].b.second = d;
s.lines[1].b.first = s.lines[3].b.first = s.lines[2].a.first = s.lines[2].b.first = c;
all.push(s);
if(!ans)
for(int i = 0; i < 4; i++)
if(isIncludeZero(s.lines[i])) ans = -1;
}
while (!all.empty()) {
g.push(all.front());
all.pop();
while (!g.empty()) {
s = g.front();
g.pop();
n = all.size();
for (int i = 0; i < n; i++) {
tmp = all.front();
all.pop();
cross(s,tmp) ? g.push(tmp) : all.push(tmp);
}
}
++ans;
}
printf("%d", ans);
}
|
