High-speed diameter for the ring road#4775
The new mayor of Flatburg, Ivan Kotyanin, has prioritized addressing the city's traffic congestion. Like many large cities, Flatburg features a ring road, which in this case is a monotone polygon. A polygon is considered monotone if every line that runs strictly from north to south intersects it at no more than two points.
Following a meeting with the city government, a decision was made to construct a new highway—a high-speed route that will run strictly from north to south, connecting two points on the ring road.
In addition to alleviating traffic congestion, the goal is to set a new record for the longest north-to-south highway. To achieve this, the highway must be at least kilometers long. Given the constraints of Flatburg's budget, the plan is to construct a road that is exactly kilometers in length.
The Minister of Transport in Flatburg has been tasked with presenting the mayor with all possible options for constructing the new road. To begin, he needs to determine the number of ways the highway can be built. Your task is to assist the minister in this calculation.
The first line of the input contains two integers: , the number of vertices in the polygon that defines the ring road (3 \leq n \leq 100\,000), and , the desired length of the new highway (1 \leq d \leq 10^8).
The next lines provide the coordinates of the vertices, with each line containing two integers and (-10^8 \leq x, y \leq 10^8). The vertices are listed in counterclockwise order.
Lines running from north to south are defined by the equation x = c for some . The polygon provided is monotone.
In the output, print the number of ways to construct an additional highway of exactly kilometers. If there are infinitely many ways to construct it, print Infinity.
Example 1