Codah ClubTrain. Submit. Improve.
Sign in
English
#0006CE

Koncert

Content with your help in conquest of Delta galaxy, Mrkvica, Terrifying space conqueror, Enslaver of worlds and Ruler of galaxies made sure you would get a VIP ticket for his favourite space-rock band concert. By the grace of Mrkvica you are allowed to pick any seat in the first row so you can fully enjoy enchanting melodies coming from the stage. However, it matters which seat you will take.


According to the tradition of the planet where the concert is being held, the stage has to be in a shape of a polygon, with its front side parallel to the first row. As it doesn't have to be a convex polygon, you might not be able to see the whole stage from some seat - a dreadful scenario you must not allow to be happen. Find the number of seats in first row from which you can see the whole stage.


We say that point A is visible from point B if the segment AB does not intersect any side of the polygon.



InputOn the first line of input there is integer N ( 3 \leq N \leq 500 000), the number of vertices of the polygon representing the stage.
Next N lines each contain two integers which are x and y coordinates of their respective vertex. All coordinates will be \leq2\cdot10^{6} by their absolute value.
The first two vertices in the input represent the side of the polygon representing the front row. We assume that the side is parallel to the x-axis.
We also assume that all other vertices are all either above or below the first side and they are given in clockwise order.
No three consecutive vertices will be collinear.


OutputOutput the number of first-row seats such that whole stage is visible from their position. Seats are placed only on integer coordinates.


Input
5
4 8
8 8
9 4
4 0
0 4
Output
5


Input
5
4 8
5 8
5 4
7 4
2 2
Output
0


Input
5
0 4
5 4
2 2
4 0
0 0
Output
1

Submit solution

Coming later

The grading service will be connected in a later migration step. You can inspect the task and your previous results now.