A border without loops
A mapping program has simplified the border of a plot, a closed polyline, and must now check that the border is still a border: it nowhere crosses or touches itself. Adjacent sides meet only at their shared vertex; non-adjacent ones have no common points at all. A vertex on a straight stretch of a side, where two adjacent sides lie on one line and continue each other, is allowed, but a side that goes back along the previous one is not.
Input
The first line holds n (3 ≤ n ≤ 105), the number of vertices. Then n lines: the vertex coordinates x y in traversal order, integers, 0 ≤ x, y ≤ 106. The last vertex is connected to the first. Adjacent vertices, including the last and the first, are distinct.
Output
YES if the border neither crosses nor touches itself, otherwise NO.
Examples
Example 1
4 0 0 4 0 4 3 0 3
YES
Example 2
4 0 0 4 3 4 0 0 3
NO
Limits
- Time · Python
- 11500 ms
- Time · Go
- 1000 ms
- Memory
- 256 MB
- Judging
- 12 tests
Walkthrough
Open it step by step: each step gives away a little more. You can jump straight to the solution, but a problem solved with one hint stays with you longer.
1Hint 1
Checking all pairs of sides is 5 · 109 pairs. But if two sides cross, then somewhere to the left of the crossing point a vertical line meets them side by side, with no sides between them.
2Hint 2
It is enough to find at least one intersection, not all of them. So crossing points need not be events: the events are only the vertices, and until the first intersection is found the order of the sides on the line does not change.
3The idea
The Shamos–Hoey algorithm, a special case of the sweep line. Visit the vertices from left to right (at equal x, bottom to top). The state is the sides crossed by the vertical, in order from bottom to top. At a vertex, the sides ending there leave the state, the starting ones take their place, and only the new pairs of neighbours are checked. If no check found a common point, there are no intersections.
4Walkthrough
First two special cases: a vertex that occurs twice, and a side that goes back along the previous one (the cross product of adjacent sides is zero and the dot product positive). After that a side is stored by its ends from left to right. At vertex q, a binary search finds the sides in the state passing through q: the position of a side relative to q is the sign of a cross product. If among them there is a side of which q is not a vertex, the vertex lies on another side, and the answer is NO. Otherwise these are the two sides of the vertex itself; replace them with the starting sides ordered by slope (a vertical one above all), and check the neighbours below and above. All computations are in integers: the products are at most 1012.
4+Solution
5Complexity
O(n log n) comparisons: sorting the vertices and a binary search per vertex. Insertion into an array shifts the tail, but that is a single memmove; on the comb of test 7, where the vertical crosses half the sides at once, the shifts do not become the bottleneck.
6Common mistakes
- All pairs. This is
wrong.py: on a star of a hundred thousand vertices it runs out of time. - Checking only on insertion. When a side leaves, its neighbours below and above become neighbours of each other, and they must be checked too.
- Touching at a vertex. A vertex lying on another side is also an intersection (test 8: the tip of a tooth lies exactly on the side of the neighbouring one). It is caught by the check “another side passes through q”.
- Vertical sides. They have no “height on the vertical”; if vertices are compared first by x and then by y, a vertical side runs from bottom to top and at its lower vertex takes its place above all the other sides from there.
- Floating-point numbers. Touching means a cross product equal to zero; in integers that is exact.
Algorithms behind it
O((n + k) log n)
3 problems
GEO
Algorithm
Segment intersection
Where two segments meet, exactly, in fractions; and how to find all meetings among thousands of segments without trying every pair.
O(1) per pair; O(n²) by brute force for n segments
2 problems