### PROBLEM LINK

### DIFFICULTY

HARD

### PREREQUISITES

Computational Geometry

Pick’s Theorem

Cyrus Beck’s Line Clipping Algorithm

Sweep Line Algorithm

Line Segment Intersection

### PROBLEM

You are given a convex polygon whose vertices are **lattice points** on the **x-y plane**. You are also given several **line segments** in the **x-y plane** whose endpoints are **lattice points**. On each **lattice point** on a line (and the endpoint of a line) and also **on or inside the polygon**, you place a **Needle**. Lines include the ones that form the polygon.

On all other **lattice points** inside the polygon, you place a **Pin**. Find the number of **Needles** placed, and the number of **Pins** placed.

### EXPLANATION

Pick’s Theorem states that

Area of polygon = number of internallattice points+ number of boundarylattice points/ 2 - 1

We can find the number of **lattice points** on a line segment from **(x _{1},y_{1}) to (x_{2},y_{2})** as

GCD( abs(x_{1}- x_{2}), abs(y_{1}- y_{2}) )

We do not place needles on the portion of the line segment that lies outside the polygon. Thus, we must clip the line segments to **lattice points** that lie inside the polygon.

The linked resource uses the **parametric notation of a line segment**. All the calculations can be done purely on integers to allow for finding the clipped lines very accurately. This may be achieved by maintaining the value of the parameter as a **fraction** - integer numerator and denominator.

- Lines that are parallel to an edge of the polygon and on, or outside the polygon, can be simply ignored

The expected time complexity for this step was **O(N*P)**, where **P** is the number of edges in the polygon.

Doing so, we are able to calculate the number of needles on the boundary of the polygon, and on the line segments inside the polygon. But, several line segments may have **intersection points** among them which are also **lattice points**. We must reduce our count of needles by the number of such intersections.

Intersections within a set of lines can be found using a **plane sweep algorithm**. The idea is elementary in books that deal with **Computational Geometry**. I personally found this resource very useful in implementing the plane sweep algorithm to report the intersection points.

Implementing this algorithm correctly and accurately (handling all the **degeneracies** possible) is the most difficult part of solving this problem. It is very well researched though, so there is no scarcity in resources describing a solution.

The expected time complexity for this step was **O((N + I) log N)**, where **I** is the number of intersection points.

Lastly, the number of pins can be found by reducing the count of needles from the number of internal **lattice points**, found using the Pick’s Theorem above.

### SETTER’S SOLUTION

Can be found here.

### TESTER’S SOLUTION

Will be uploaded shortly.