Crazy Fences
InterviewTime limit1sMemory limit128 MB
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 () 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 () 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 and .
- Lines to : each line contains four integers , , , , describing a fence running from point to point . Every fence is vertical () or horizontal (). All coordinates lie between and .
- Lines to : each line contains two integers and , the position of a cow. All coordinates lie between and .
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.