Largest Community Problem

Farmer John has re‐designed his farm after visiting a modern art museum. He has moved N fence segments (with \(1 \le N \le 1000\)) among his pastures. Each fence is given as a line segment in the 2D plane, and if two fences meet, they do so only at their endpoints. Moreover, each fence touches exactly one other fence at each of its two endpoints.

Farmer John also has C cows (with \(1 \le C \le 1000\)) located at distinct points in the plane (and none lying on any fence). Two cows are in the same community if one can walk to the other without crossing (touching) any fence. In other words, the fences partition the plane into several regions, and cows in the same region form one community. Your task is to determine the size of the largest community (i.e. the maximum number of cows in a single region).

Hint: The fence segments form cycles (simple polygons) that may be nested. A typical approach is to first reconstruct the cycles, then for each cow determine which cycles (polygons) it lies within using a point-in-polygon method (e.g. ray casting). Cows sharing the same "signature" of inside/outside with respect to all cycles belong to the same community.

inputFormat

The first line contains two integers \(N\) and \(C\) representing the number of fences and the number of cows respectively.

The next \(N\) lines each contain four integers: x1 y1 x2 y2, representing the endpoints of a fence segment.

The following \(C\) lines each contain two integers: x y, representing the coordinates of a cow.

outputFormat

Output a single integer representing the size of the largest community (i.e. the maximum number of cows that lie in the same region).

sample

3 3
0 0 10 0
10 0 5 10
5 10 0 0
1 1
6 2
20 20

2