페이지가 로드되지 않나요? 여기를 눌러보면 고쳐질 수도 있어요.
Placeholder

#3802

Crazy Fences 1초 128MB

문제

Problem 1: Crazy Fences [Brian Dean, 2012]

After visiting a modern art museum, Farmer John decides to re-design his farm by moving all of the N (1 <= N <= 1000) fences between his pastures! Each fence is describe by a line segment in the 2D plane. If two fences meet, they do so only at their endpoints. Each fence touches exactly two other fences, one at both endpoints.

FJ has C cows (1 <= C <= 1000) 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.

PROBLEM NAME: crazy


입력

* Line 1: Two space-separated integers N and C.

* Lines 2..1+N: Each line contains four integers: x1, y1, x2, y2, indicating a fence from point (x1,y1) to point (x2,y2). All coordinates are integers in the range 0..1,000,000.

* Lines 2+N..1+N+C: Each line contains two integers x and y describing the location of a cow. All coordinates are integers in the range 0..1,000,000.


출력

* Line 1: The number of cows in the largest community.


예제1

입력
10 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 1
출력
2

INPUT 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 members of a community of size 1.


출처

USACO 2012 December Silver

역링크 공식 문제집만