[Link] https://www.acmicpc.net/problem/2162
Model: intersection graph and connected components
Treat each input segment as a vertex in a graph, and connect two vertices exactly when their closed segments intersect. A group is a connected component of this graph: segments belong to the same group even when they do not directly intersect, as long as there is a chain of intersecting segments between them. Therefore, test every pair of segments and union the pair in a disjoint-set union (DSU) structure when they intersect. At the end, the number of DSU roots is the number of groups, and the largest DSU component size is the largest group size.
Exact closed-segment intersection
For points A, B, and C, the signed cross product (B.x - A.x) * (C.y - A.y) - (B.y - A.y) * (C.x - A.x) is positive or negative according to which side of directed line AB contains C; zero means collinear. Two segments properly cross in their interiors only when the two endpoints of each segment have strictly opposite orientation signs relative to the other segment. Compare signs directly; do not multiply cross products, since multiplying large values can overflow even when each cross product fits.
Zero orientations cover endpoint contact and collinear cases. For each zero orientation, check whether that point lies inside the other segment’s inclusive x- and y-coordinate bounds. This also handles collinear overlap, separated collinear segments, and degenerate point segments; merely being on the same infinite line is not enough for finite segments to intersect.
The official limits are 1 ≤ N ≤ 3,000 and each coordinate is in [-5,000, 5,000]. A coordinate difference has absolute value at most 10,000, so each product in the cross product has absolute value at most 10^8; their difference has absolute value at most 2 × 10^8. This fits safely in signed 64-bit long long.
There are O(N^2) segment pairs. Each intersection test takes constant time, and each DSU operation takes amortized O(α(N)) time with path compression and union by size. The total time is O(N^2 α(N)); the input segments and DSU arrays use O(N) auxiliary space.
C++17
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
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
#include <algorithm>
#include <iostream>
#include <vector>
using namespace std;
struct Point {
long long x;
long long y;
};
struct Segment {
Point a;
Point b;
};
long long cross(const Point& a, const Point& b, const Point& c) {
return (b.x - a.x) * (c.y - a.y) - (b.y - a.y) * (c.x - a.x);
}
int orientation(const Point& a, const Point& b, const Point& c) {
const long long value = cross(a, b, c);
if (value > 0) return 1;
if (value < 0) return -1;
return 0;
}
bool onSegment(const Point& a, const Point& b, const Point& p) {
return min(a.x, b.x) <= p.x && p.x <= max(a.x, b.x) &&
min(a.y, b.y) <= p.y && p.y <= max(a.y, b.y);
}
bool oppositeSigns(int a, int b) {
return (a < 0 && b > 0) || (a > 0 && b < 0);
}
bool intersects(const Segment& first, const Segment& second) {
const Point& a = first.a;
const Point& b = first.b;
const Point& c = second.a;
const Point& d = second.b;
const int abC = orientation(a, b, c);
const int abD = orientation(a, b, d);
const int cdA = orientation(c, d, a);
const int cdB = orientation(c, d, b);
if (oppositeSigns(abC, abD) && oppositeSigns(cdA, cdB)) return true;
if (abC == 0 && onSegment(a, b, c)) return true;
if (abD == 0 && onSegment(a, b, d)) return true;
if (cdA == 0 && onSegment(c, d, a)) return true;
if (cdB == 0 && onSegment(c, d, b)) return true;
return false;
}
class DSU {
public:
explicit DSU(int n) : parent(n), size(n, 1) {
for (int i = 0; i < n; ++i) parent[i] = i;
}
int find(int x) {
if (parent[x] != x) parent[x] = find(parent[x]);
return parent[x];
}
void unite(int a, int b) {
a = find(a);
b = find(b);
if (a == b) return;
if (size[a] < size[b]) swap(a, b);
parent[b] = a;
size[a] += size[b];
}
int componentSize(int root) const {
return size[root];
}
private:
vector<int> parent;
vector<int> size;
};
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n;
cin >> n;
vector<Segment> segments(n);
for (Segment& segment : segments) {
cin >> segment.a.x >> segment.a.y >> segment.b.x >> segment.b.y;
}
DSU dsu(n);
for (int i = 0; i < n; ++i) {
for (int j = i + 1; j < n; ++j) {
if (intersects(segments[i], segments[j])) dsu.unite(i, j);
}
}
int groupCount = 0;
int largestGroup = 0;
for (int i = 0; i < n; ++i) {
if (dsu.find(i) == i) {
++groupCount;
largestGroup = max(largestGroup, dsu.componentSize(i));
}
}
cout << groupCount << '\n' << largestGroup << '\n';
return 0;
}