BOJ 2162 선분 그룹

1 개요

BOJ 2162 선분 그룹

• 백준 온라인 저지 2162번 문제
• BOJ 39단계

2 C++

#include <iostream>
using namespace std;

struct Point {
    int x, y;
    bool operator<=(Point const &a) {
        if(x == a.x) {
            return y <= a.y;
        }
        return x <= a.x;
    }
};
struct Line {
	int x1, y1, x2, y2;
};

int N;
Line L[3000];
int parent[3000];
int C[3000] = {};

int getParent(int a) {
	if (a == parent[a]) return parent[a];
	return parent[a] = getParent(parent[a]);
}

void unionSet(int a, int b) {
	a = getParent(a);
	b = getParent(b);
	if (a < b) {
	    parent[b] = a;
	} else {
	    parent[a] = b;
	}
}

int ccw(const Point &a, const Point &b, const Point &c) {
    int res = (a.x*b.y + b.x*c.y + c.x*a.y) - (b.x*a.y + c.x*b.y + a.x*c.y);
    if(res > 0) return 1;
    if(res < 0) return -1;
    return 0;
}

bool intersect(Line l1, Line l2) {
    Point p1 = {l1.x1, l1.y1};
    Point p2 = {l1.x2, l1.y2};
    Point p3 = {l2.x1, l2.y1};
    Point p4 = {l2.x2, l2.y2};
    int std1 = ccw(p1, p2, p3) * ccw(p1, p2, p4);
    int std2 = ccw(p3, p4, p1) * ccw(p3, p4, p2);
    if(std1 <= 0 && std2 <= 0) {
        if(std1 == 0 && std2 == 0) {
            if(p2 <= p1) swap(p1, p2);
            if(p4 <= p3) swap(p3, p4);
            return p1 <= p4 && p3 <= p2;
        }
        return true;
    }
    return false;
}
 
void solve() {
    for(int i=0; i<N; i++) {
        for(int j=0; j<i; j++) {
            if(intersect(L[i], L[j])) {
                unionSet(i, j);
            }
        }
    }
    for (int i=0; i<N; i++) {
		C[getParent(i)]++;
	}
	int cnt = 0;
	int mx = 0;
	for (int i=0; i<N; i++) {
		if(C[i] > 0) cnt++;
		if(C[i] > mx) mx = C[i];
	}
	cout << cnt << '\n' << mx;
}
 
int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cin >> N;
    for(int i=0; i<N; i++) {
        cin >> L[i].x1 >> L[i].y1 >> L[i].x2 >> L[i].y2;
        parent[i] = i;
    }
    solve();
}