NPIN - Editorial

[gamabunta]

PROBLEM LINK

Practice
Contest

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 internal lattice points
  + number of boundary lattice points / 2
  - 1

We can find the number of lattice points on a line segment from (x₁,y₁) to (x₂,y₂) as

GCD( abs(x1 - x2), abs(y1 - y2) )

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.

[vinayak_garg]

It would be nice if pperm, Anton or djdolls could explain their approach.

Below I give one small test case.

Input

6 5
1 0
6 1
8 4
5 7
0 7
-2 4
1 7 4 1
7 7 0 0
4 6 2 4
-1 5 5 2
4 4 1 1

Output

25 31    

[mugurelionut]

Where is the condition regarding the 16 “squares” used in the official solution ? It is my impression that the sweep line algorithm for segment intersections would work in any situation, right?

I can tell you where I kind of used it in my solution. I used a quadtree-like approach (the root contains a large enough square). Then I would keep decomposing the space further and further until:

1. I reached a zone of the quadtree which did not intersect too many segments (e.g. <= 200) : then an O(nr of segments^2) algorithm for segment intersection would work (restricted to the parts of the segments “clipped” by the current zone of the quadtree).

2. I reached a zone of only 1 point in the quadtree which intersects at least 2 segments => this is an intersection point and can be counted as such directly.

This approach works very well, except, possibly, in some very degenerate cases - but the 16 “squares” conditions ensured no such cases would exist.

[vinayak_garg]

@mugurelionut: Thanks for sharing your approach!

Without 16 squares condition, the problem would be much harder. Like you said - this condition eliminated some difficult cases.
Similarly, coding the sweep line algorithm which handles the general case i.e without this condition (plus limit on length of line) would be very complex (at least for me).

Specifically in my solution (modified Bentley-Ottman) the condition simplified the part checking intersection of current (event) line with active lines.