Counting Cows

Time limit1sMemory limit1024 MB

Summary

Given cows and fence segments that split the plane into fields, find the largest cow count in any field, with the outside region as a candidate.

Level: Medium6 of 10
Topics: Geometry, Graph, Sorting
Solved: No attempts yet

Problem

Farmer John's farm has several fenced-in fields, and FJ wants to know which of them currently contains the most cows. $N$ ( $1 \le N \le 100$ ) cows in total live at various integer coordinates in the two-dimensional plane that is the farm. The farm contains $K$ ( $1 \le K \le 1000$ ) fences. Each fence is a line segment of positive length with integer coordinates for its endpoints. If fences intersect, they may do so only at their endpoints. No cow lies on any fence or shares a point with another cow.

A field is an area of the farm that is completely enclosed by fences. A cow belongs to the smallest field (by area) that encloses it. A cow that is not inside any fenced-in field belongs to the "master" field. Report the number of cows in the field that contains the most cows, counting the "master" field as a candidate.

In the three figures below, the answers are (a) 2, (b) 2, and (c) 1.

   +-------+               -------+                cow 1
   | cow 1 +--------+       cow 1 |               ________
   |          cow 2 |             |  cow 2       /       |
   +----------------+      -------+             +--------+

         (a)                  (b)                (c)

Input

The first line contains two integers, $N$ and $K$ . The next $N$ lines each contain the $x$ and $y$ coordinates of a cow. The next $K$ lines each contain four integers, the coordinates of the two endpoints of a fence.

Output

Print a single integer: the number of cows in the field that contains the most cows.

Examples1

Example 1
Input
```
2 3
4 5
10 3
3 0 7 0
7 0 7 6
0 6 7 6
```
Expected output
```
2
```