백준2162 선분 그룹

작성일 | In

문제 링크

  • http://icpc.me/2162

사용 알고리즘

  • CCW
  • BFS

시간복잡도

  • O(n2)

풀이

(이 문제)와 비슷한 문제입니다.

이 문제는 교차하는(혹은 접하거나 만나는) 선분끼리 같은 그룹으로 묶었을 때, 그룹의 개수 등을 구하는 문제입니다.
선분을 정점으로 생각하면서, 교차하는 선분을 간선으로 이어준 뒤, BFS나 DFS로 연결 요소의 개수 등과 같은 정보들을 구해주면 됩니다.

선분의 교차 여부는 CCW를 이용해 할 수 있습니다.

전체 코드

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
#include <bits/stdc++.h>
#define x first
#define y second
using namespace std;

typedef pair<int, int> p;
typedef pair<p, p> pp;
typedef long long ll;

vector<int> g[3010]; //graph
vector<pp> line; //line

long long ccw(p a, p b){
	return a.x*b.y - a.y*b.x;
}

int ccw(p a, p b, p c){
	long long res = ccw(make_pair(b.x - a.x, b.y - a.y), make_pair(c.x - a.x, c.y - a.y));
	if (res > 0) return 1;
	if (res < 0) return -1;
	return 0;
}

bool chk(pp aa, pp bb){
	p a = aa.first, b = aa.second;
	p c = bb.first, d = bb.second;

	int ab = ccw(a, b, c) * ccw(a, b, d);
	int cd = ccw(c, d, a) * ccw(c, d, b);

	if(ab==0 && cd==0){
		if(b<a) swap(a, b);
		if(d<c) swap(c, d);
		return c<=b && a<=d;
	}

	return ab<=0 && cd<=0;
}

int visit[3010];
int bfs(int s){
	queue<int> q;
	q.push(s);
	visit[s] = 1;
	int ret = 1;

	while(!q.empty()){
		int poped = q.front(); q.pop();
		for(auto j : g[poped]){
			if(!visit[j]){
				q.push(j); ret++;
				visit[j] = 1;
			}
		}
	}
	return ret;
}

int main(){
	ios_base::sync_with_stdio(0); cin.tie(0);
	int n;
	cin >> n;
	line = vector<pp>(n);
	for(int i=0; i<n; i++){
		cin >> line[i].first.x >> line[i].first.y >> line[i].second.x >> line[i].second.y;
	}

	for(int i=0; i<n; i++){
		for(int j=0; j<i; j++){
			if(chk(line[i], line[j])){
				g[i].push_back(j); g[j].push_back(i);
			}
		}
	}

	int maxi = 0, cnt = 0;
	for(int i=0; i<n; i++){
		if(!visit[i]){
			cnt++;
			maxi = max(maxi, bfs(i));
		}
	}

	cout << cnt << "\n" << maxi;
}