BOJ 2162: 선분 그룹 작성일 2020-03-01 https://www.acmicpc.net/problem/2162 3월동안 210문제 풀기 (4/210) Union-Find + 선분 교차 123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144#include <bits/stdc++.h> using namespace std; const double EPS = 1e-9; struct Vector { double x, y; Vector() { this->x = 0, this->y = 0; } Vector(int x, int y) { this->x = x, this->y = y; } Vector(const Vector& v1) { x = v1.x, y =v1.y; } Vector& operator+=(const Vector &other) { x += other.x; y += other.y; return *this; } Vector& operator-=(const Vector &other) { x -= other.x; y -= other.y; return *this; } Vector& operator*=(const double C) { x *= C; y *= C; return *this; } Vector& operator/=(const double C) { x /= C; y /= C; return *this; } Vector operator+(const Vector &other) const { return Vector(*this) += other; } Vector operator-(const Vector &other) const { return Vector(*this) -= other; } Vector operator*(const double C) const { return Vector(*this) *= C; } Vector operator/(const double C) const { return Vector(*this) /= C; } }; double cross(Vector v1, Vector v2) { return v1.x * v2.y - v1.y * v2.x; } double ccw(Vector va, Vector vb) { double v = cross(va, vb); if(abs(v) < EPS) return 0; if(v > 0) return 1; if(v < 0) return -1; } double ccw(Vector vr, Vector va, Vector vb) { return ccw(va - vr, vb - vr); } bool project(double x1, double x2, double x3, double x4) { if(x1 > x2) swap(x1,x2); if(x3 > x4) swap(x3,x4); return max(x1,x3) <= min(x2, x4); } bool segmentInter(Vector v1, Vector v2, Vector v3, Vector v4) { double v1Root = ccw(v1, v2, v3) * ccw(v1, v2, v4); double v3Root = ccw(v3, v4, v1) * ccw(v3, v4, v2); if (v1Root == 0 && v3Root == 0) return project(v1.x, v2.x, v3.x, v4.x) && project(v1.y, v2.y, v3.y, v4.y); return v1Root <= 0 && v3Root <= 0; } typedef array<Vector, 2> Segment; bool segmentInter(Segment& s1, Segment& s2) { return segmentInter(s1[0], s1[1], s2[0], s2[1]); } class DisjointSet { public: int N, num; vector<int> parent, rank, count; DisjointSet(int n): N(n), num(n), parent(n), rank(n), count(n,1) { iota(parent.begin(), parent.end(), 0); } int find(int x) { return parent[x] = (parent[x] == x ? x : find(parent[x])); } void uni(int a, int b) { a = find(a); b = find(b); if(a == b) return; if(rank[a] > rank[b]) swap(a,b); parent[a] = b; if(rank[a] == rank[b]) rank[b]++; count[b] += count[a]; count[a] = 0; num--; } }; int main() { int N, x1, y1, x2, y2; scanf("%d", &N); vector<Segment> arr; arr.reserve(N); for(int i = 0; i < N; i++) { scanf("%d %d %d %d", &x1, &y1, &x2, &y2); Vector v1 = {x1,y1}, v2 = {x2,y2}; arr.push_back({v1, v2}); } DisjointSet dset(N); for(int i = 0; i < N; i++) { for(int j = i+1; j < N; j++) { if(segmentInter(arr[i], arr[j])) dset.uni(i,j); } } printf("%d\n", dset.num); int ans = 0; for(int x : dset.count) ans = max(ans, x); printf("%d\n", ans); }