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