레이팅 미적용현대 미술관에 다녀온 농부 존(Farmer John)은 목초지 사이의 N개 (1 <= N <= 1000)의 울타리를 모두 옮겨서 농장을 다시 설계하기로 했다! 각 울타리는 2차원 평면의 선분으로 표현된다. 두 울타리가 만난다면 오직 끝점에서만 만난다. 각 울타리는 정확히 두 개의 다른 울타리와 양쪽 끝점에서 각각 하나씩 맞닿아 있다.
FJ의 농장에는 C마리 (1 <= C <= 1000)의 소가 있다. 각 소는 2차원 평면에서 어떤 울타리 위도 아닌 점에 있으며, 어떤 두 소도 같은 점에 있지 않다. 한 소가 어떤 울타리도 건드리지 않고 다른 소에게 걸어갈 수 있으면, 두 소는 같은 공동체에 속한다고 한다. 가장 큰 공동체의 크기를 알아내는 것을 FJ에게 도와주자.
첫째 줄: 공백으로 구분된 두 정수 N과 C.
둘째 줄부터 1+N번째 줄까지: 각 줄에 점 (x1,y1)에서 점 (x2,y2)까지의 울타리를 나타내는 네 정수 x1, y1, x2, y2가 주어진다. 모든 좌표는 0..1,000,000 범위의 정수이다.
2+N번째 줄부터 1+N+C번째 줄까지: 각 줄에 소의 위치를 나타내는 두 정수 x와 y가 주어진다. 모든 좌표는 0..1,000,000 범위의 정수이다.
가장 큰 공동체에 속한 소의 수.
crazy.in · 출력을 쓸 파일 crazy.out10 4
0 0 10 0
10 0 10 10
0 0 0 10
10 10 0 10
8 8 9 8
9 8 8 9
8 9 8 8
2 7 3 2
3 2 7 5
7 5 2 7
15 3
1 4
4 5
7 12Input details: There are 10 fences and 4 cows. The fences form a square containing two triangles.
Output details: Cows #2 and #4 belong to the same community. Cows #1 and #3 are each in a community of size 1.
riseoj 작성
출처 올림피아드 > USACO > 2012-2013 > December > Silver