[Link] https://www.acmicpc.net/problem/2162
CCW + Union Find
Point: Line AB and CD : ccw(ABC) and ccw(ABD)
if(ccw(ABC) == ccw(ABD) == 0) compare the range A B C D, C D A B
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
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
#include <algorithm>
#include <iostream>
#include <vector>
#include <map>
#include <set>
#include <queue>
#include <cstring>
#include <stack>
#include <cmath>
// #include <bits/stdc++.h>
using namespace std;
#define FASTIO ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0)
#define command_param int argc, char *argv[]
#define for0(i, n) for(int i = 0; i < n; i++)
#define for1(i, n) for(int i = 1; i < n; i++)
#define fori(s, e) for(int i = s; i < e; i++)
#define ll long long
#define endl "\n"
#define nulls '\0'
#define dkdk " "
// const int MAX = 2002;
// const int INF = 987654321;
// const int OPPOSITE = 1;
// const int ONEZERO = 2;
// const int TWOZERO = 3;
// const int SAMESIDE = 4;
struct line {
pair<int, int> s, e;
};
int n;
vector<line> lines;
vector<int> ancestor;
ll ccw(pair<int,int> p1, pair<int,int> mid, pair<int,int> p2) {
ll outer = (ll)p1.first * mid.second + (ll)mid.first *p2.second + (ll)p2.first * p1.second;
outer -= ((ll)mid.first * p1.second + (ll)p1.first *p2.second + (ll)p2.first * mid.second);
return outer;
}
bool lines_meet(line l1, line l2) {
ll ccw1 = ccw(l1.s, l1.e, l2.s) * ccw(l1.s, l1.e, l2.e);
ll ccw2 = ccw(l2.s, l2.e, l1.s) * ccw(l2.s, l2.e, l1.e);
if(ccw1 == 0 && ccw2 == 0) {
int ax = l1.s.first, bx = l1.e.first, cx = l2.s.first, dx = l2.e.first;
int ay = l1.s.second, by = l1.e.second, cy = l2.s.second, dy = l2.e.second;
if(ax > bx) swap(ax, bx); if(cx > dx) swap(cx, dx);
if(ay > by) swap(ay, by); if(cy > dy) swap(cy, dy);
return ax <= dx && cx <= bx && ay <= dy && cy <= by;
}
return ccw1 <= 0 && ccw2 <= 0;
}
int get_parent(int a) {
if(a == ancestor[a]) return a;
return ancestor[a] = get_parent(ancestor[a]);
}
void unify(int a, int b) {
int pa = get_parent(a), pb = get_parent(b);
if(pa >= pb) ancestor[pa] = pb;
else ancestor[pb] = pa;
}
int main() {
FASTIO;
cin >> n;
for0(i, n) ancestor.push_back(i);
lines.resize(n);
for0(i, n) cin >> lines[i].s.first >> lines[i].s.second >> lines[i].e.first >> lines[i].e.second;
for0(i, n) {
for(int j = i+1; j < n; j++) {
if(lines_meet(lines[i], lines[j])) unify(i, j);
}
}
int cnt = 0;
map<int, int> union_cnt;
for0(i, n) {
int anc_idx = get_parent(i);
if(union_cnt.find(anc_idx) == union_cnt.end()) union_cnt[anc_idx] = 1;
else union_cnt[anc_idx]++;
}
int max_v = 0;
for(map<int, int>:: iterator iter = union_cnt.begin(); iter!=union_cnt.end(); iter++) {
max_v = max(max_v, iter->second);
}
cout << union_cnt.size() << endl << max_v;
return 0;
}