This page is still under construction.

Parts of this page are still being built. What you see may change.

Crazy Fences

Interview

Time limit1sMemory limit128 MB

Summary
Given horizontal and vertical fences that meet only at endpoints and points for cows, find the largest set of cows that can reach each other without touching a fence.
Level

Medium6 of 10

Topics
Geometry, Graph, Union-find, BFS
Solved
No attempts yet

Problem

A farmer redesigns the farm by setting up NN (1≤N≤5001 \le N \le 500) new fences between the pastures. Each fence is a horizontal or vertical line segment in the 2D plane. If two fences meet, they meet only at their endpoints.

There are CC (1≤C≤5001 \le C \le 500) cows on the farm. Each cow stands at a point that lies on no fence, and no two cows share the same point. Two cows belong to the same community if one can walk to the other without ever touching a fence. Determine the size of the largest community.

Input

  • Line 1: two space-separated integers NN and CC.
  • Lines 22 to N+1N+1: each line contains four integers x1x_1, y1y_1, x2x_2, y2y_2, describing a fence running from point (x1,y1)(x_1, y_1) to point (x2,y2)(x_2, y_2). Every fence is vertical (x1=x2x_1 = x_2) or horizontal (y1=y2y_1 = y_2). All coordinates lie between 00 and 1,000,0001{,}000{,}000.
  • Lines N+2N+2 to N+1+CN+1+C: each line contains two integers xx and yy, the position of a cow. All coordinates lie between 00 and 1,000,0001{,}000{,}000.

Output

  • Line 1: the number of cows in the largest community.

Hint

Two cows share a community exactly when a continuous path connects their positions without ever touching a fence. Because fences meet only at their endpoints, a fence with a free (dangling) end does not fully seal off a region, so a cow can simply walk around that open end. Only fences that together enclose an area separate one community from another.

Examples1

  1. Example 1

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