Crazy Fences (Bronze)
브론즈 II의견: 0
After visiting a modern art museum, Farmer John decides to re-design his farm by moving all of the N (1 <= N <= 500) fences between his pastures! Each fence is described by either a horizontal or a vertical line segment in the 2D plane. If two fences meet, they do so only at their endpoints.
FJ has C cows (1 <= C <= 500) on his farm. Each cow resides at a point in the 2D plane that is not on any fence, and no two cows reside at the same point. Two cows are said to be in the same community if one could walk to the other without touching any fences. Please help FJ determine the size of the largest community.
Line 1: Two space-separated integers, N and C.
Lines 2..1+N: Each line contains four integers: x1, y1, x2, y2. These describe a fence running from point (x1,y1) to point (x2,y2). Each fence is either vertical (x1=x2) or horizontal (y1=y2). All coordinates are in the range 0 .. 1,000,000.
Lines 2+N..1+N+C: Each line contains two integers x and y describing a cow at position (x,y). All coordinates are in the range 0 .. 1,000,000.
The number of cows in the largest community.
crazy.incrazy.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
평가 및 의견
Crazy Fences (Bronze)
Log in to rate problems.
아직 의견이 없습니다. 자격이 된다면 위 양식에서 가장 먼저 평가해 보세요.
풀이 제출
Crazy Fences (Bronze)