Hide

Problem D
Greedy Cows

/problems/greedycow/file/statement/en/img-0001.jpg
Photo by Iain McDonald
Old MacDonald had a farm, and on that farm he had $n$ cows. It is now time to let the cows graze. However, some cows are very greedy and eat the other cows’ grass. Being a clever old man, MacDonald decides to split his pasture into several regions. The pasture is surrounded by a great, convex fence.

To split the pasture, he will select a number of points on the surrounding fence, and set up yet more fences between all pairs of selected points, except the points that lie on the same side of the surrounding fence. These new fences may cross. Now, this will create a number of mini-pastures in the pasture (see Figure 1).

MacDonald wants to minimize the number of points selected (not the total fence length, as you might have thought). How many points does he need to select in order to have at least one mini-pasture for each cow? Some of these mini-pastures might be tiny: that doesn’t bother Old MacDonald, but only mini-pastures with positive area count.

\includegraphics[width=0.5\textwidth ]{sample}
Figure 1: A possible solution to the first sample case below.

Input

The input begins with an integer $1 \le n \le 2^{60}$, the number of cows Old MacDonald has. Then follows an integer $3 \le F \le 100$ - the number of fence posts in Old MacDonald’s fence. The next $F$ lines will contain two integers $-10^9 \le C_ x,C_ y\le 10^9$, the coordinates of the posts. The $F$ fence posts form a convex polygon with positive area, given in clockwise order.

Output

Output an integer $p$, the minimum number of points Old MacDonald needs to select, so that each cow gets at least one mini-pasture each.

Sample Input 1 Sample Output 1
5
4
0 0
0 4
4 4
4 0
4
Sample Input 2 Sample Output 2
13
5
1 3
2 3
3 2
2 1
1 1
5

Please log in to submit a solution to this problem

Log in