November Rain
Time limit1sMemory limit128 MB
Given non-intersecting sloped roof segments, compute for each segment how much rainwater (falling vertically, then sliding down slopes and shielded by segments above) drains off its lower end.
Problem
Modern buildings can have very complicated roofs. A vertical cross-section of such a roof is a set of sloping segments. When it rains, drops fall straight down from the sky onto the roof. Some segments are fully exposed to the rain, while others are partially or completely shielded by segments above them.
All the water that lands on a segment runs down along it and pours off its lower end as a single stream that falls straight down, either onto the ground or onto another segment. In particular, if a stream falls exactly on an endpoint of a segment, that segment is still considered to collect it.
To design the drainage, we want to know how much water pours off each segment. Assume that during one second, one liter of rain falls on every one-meter width of the horizontal plane.
Write a program that reads a description of a roof and, for each segment, reports the amount of water (in liters) that pours off it during one second.
Input
The first line contains an integer n (1 ≤ n ≤ 40000), the number of roof segments. Each of the next n lines contains four integers x1, y1, x2, y2 (0 ≤ x1, y1, x2, y2 ≤ 1000000, x1 < x2, y1 ≠ y2) separated by single spaces. (x1, y1) is the left endpoint of the segment and (x2, y2) is its right endpoint; x is the horizontal position and y is the height.
No two segments share a common point, and there are no horizontal segments. At most 25 segments lie above any single point of the ground.
Output
Print n lines. The i-th line contains the amount of water, in liters, that pours off the i-th segment during one second. This amount is always an integer.