Crazy Fences

Time limit1sMemory limit128 MB

Summary
Fences form disjoint closed polygons; find the largest set of cows that can reach each other without crossing a fence.
Level

Hard8 of 10

Topics
Geometry, Graph, Implementation, Brute force
Solved
No attempts yet

Problem

Farmer John is redesigning his farm by rearranging all NN fences between his pastures (1≤N≤10001 \le N \le 1000). Each fence is a straight line segment in the 2D plane. Two fences may meet only at their endpoints, and every fence meets exactly two other fences — one at each of its two endpoints. As a result, the fences form one or more disjoint closed polygons.

Farmer John has CC cows (1≤C≤10001 \le C \le 1000). Each cow stands at a point that lies on no fence, and no two cows stand at the same point. Two cows belong to the same community if one of them can walk to the other without ever crossing a fence.

Report the size of the largest community.

Input

  • Line 1: two space-separated integers NN and CC.
  • Lines 2…N+12 \dots N+1: four integers x1 y1 x2 y2x_1\ y_1\ x_2\ y_2, describing a fence from (x1,y1)(x_1, y_1) to (x2,y2)(x_2, y_2).
  • Lines N+2…N+C+1N+2 \dots N+C+1: two integers x yx\ y, the location of a cow.

All coordinates are integers from 0 to 1,000,000.

Output

  • A single integer: the number of cows in the largest community.

Hint

Because the fences form closed loops, two cows share a community exactly when the same set of loops encloses both of them. In the sample, the fences form a square that contains two triangles; two of the four cows fall inside the same set of loops and share a community, while the remaining two are each alone.

Examples3

  1. Example 1

    Input
    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
    
    Expected output
    2
    
  2. Example 2

    Input
    4 5
    0 0 10 0
    10 0 10 10
    10 10 0 10
    0 10 0 0
    5 5
    2 2
    8 8
    15 15
    15 5
    
    Expected output
    3
    
  3. Example 3

    Input
    3 5
    0 0 10 0
    10 0 5 10
    5 10 0 0
    5 3
    5 5
    4 4
    0 8
    9 8
    
    Expected output
    3