CS
Problems Base course RU

Problem

Bridges and tunnels

intersections maps and navigation geodata hashing contests

In OpenStreetMap, streets that cross at the same level must have a shared node, a junction. If there is no shared node, one street passes over the other and must have a different layer: a bridge higher, a tunnel lower. A checking program receives streets cut into segments and counts the places where the interiors of two segments cross at one point. If the segments have different layers, it is a bridge or a tunnel; if the layer is the same, an error in the data.

Touches do not count: an end of a segment on another segment is a junction or an abutment, and segments on one line with a common piece are an overlap, not a crossing. The second test is all the streets of central Almaty from OpenStreetMap: 37,315 segments in decimetres with layers.

Input

The first line holds the number of segments n (1 ≤ n ≤ 50,000). Then n lines: x1 y1 x2 y2 l, a segment’s ends and its layer. All numbers are integers, |x|, |y| ≤ 10⁶, |l| ≤ 5; a segment’s ends are distinct. Segments are pieces of streets, and in every test except the small ones the segments that cross or touch are far fewer than all pairs.

Output

Two numbers separated by a space: how many pairs of segments cross on different layers and how many on the same layer.

Examples

Example 1

Input
12
0 0 10 10 0
0 10 10 0 1
20 0 30 10 0
20 10 30 0 0
40 0 50 0 0
45 0 45 8 0
60 0 70 5 0
70 5 80 0 1
90 0 100 0 0
95 0 110 0 1
0 20 10 20 0
0 22 10 22 0
Output
1 1

Limits

Time · Python
6000 ms
Time · Go
1500 ms
Memory
256 MB
Judging
5 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 one pair is four cross products: the ends of each segment are strictly on different sides of the other. The trouble is the number of pairs: almost 700 million for 37 thousand segments. Which pairs need not be checked at all?

2Hint 2

Only segments lying close together cross. Cut the plane into cells and record each segment in the cells its bounding box touches. How do you make sure a pair that lands in several common cells is counted once?

3The idea

A uniform grid with a cell of the order of the average segment length. Check pairs only within cells, and each only in the cell containing the lower-left corner of the intersection of their bounding boxes: a pair has only one such cell, and both segments lie in it. The crossing of interiors is strict: all four cross products are nonzero and pairwise of different signs.

4Walkthrough

Take the cell size c equal to the average segment length along the larger of the axes. A segment with the box [xmin, xmax] × [ymin, ymax] lands in cells from ⌊xmin/c⌋ to ⌊xmax/c⌋ in x, and likewise in y; keep the cells in a hash table by their number. Division must round down for negative numbers too: in Python that is //, in Go you have to write it yourself.

For a pair (s, t) in cell (gx, gy) compute mx = max(min x of s, min x of t), and likewise my. If ⌊mx/c⌋ ≠ gx or ⌊my/c⌋ ≠ gy, skip it: this pair will be counted in another cell. If the boxes do not overlap, the point (mx, my) may not fall in any of their common cells, and then nobody counts the pair, which is right: such segments do not cross.

Then a strict crossing check and a count by layers. On Almaty’s streets a grid with cells the size of the average segment checks less than a thousandth of all pairs. The answer on the second test is 166 bridges and tunnels and not a single error.

4+Solution
5Complexity

O(n + P), where P is the number of pairs that ended up in common cells. On streets P is of the same order as n, but there is no guarantee: if all segments are long and stretch across the whole field, like the avenues in the fourth test, the grid degenerates into one cell and checks all pairs. The guaranteed O((n + k) log n) for k crossings comes from the Bentley–Ottmann sweep line, which has its own article.

6Common mistakes
  • All pairs in a row. Correct, but 700 million checks on the second test will not fit in the time. This is a wrong solution.
  • A pair counted in every common cell. Long segments lie in many cells, and without the rule “in one cell only” a crossing is counted several times. A set of already checked pairs also helps, but it is slower and eats memory.
  • A touch taken for a crossing. The condition “signs differ or zero” counts every letter T and every shared end, and on streets there are tens of thousands of them. The fifth test has not a single real crossing, only touches and overlaps.
  • Dividing negatives. In Go and C++ -7 / 5 equals −1, not −2, and segments left of zero land in the wrong cells.

Algorithms behind it

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 GEO Technique Sweep line Simplify the world’s coasts to 0.2° and they cross themselves in 72 places. A line moving west to east finds them all, comparing only neighbours. O((n + k) log n) 3 problems DS Data structure Hash table Search, insert and delete by key in O(1) on average: the key turns into the number of an array cell. O(1) on average 2 problems
The algorithms catalogue