CCO '20 P1 - A Game with Grundy

View as PDF

Submit solution

Points: 10 (partial)
Time limit: 1.0s
Memory limit: 1G

Problem type
Canadian Computing Olympiad: 2020 Day 1, Problem 1

Grundy is playing his favourite game — hide and seek.

His N friends stand at locations on the x-axis of a two-dimensional plane — the i-th one is at coordinates (x_i,0). Each friend can see things in a triangular wedge extending vertically upwards from their position — the i-th friend's triangular wedge of vision will be specified by two lines: one with slope of v_i/h_i and the other with slope -v_i/h_i. A friend cannot see a point that lies exactly on one of these two lines.

Grundy may choose to hide at any location (a, Y), where a is an integer satisfying L \le a \le R, and L, R, and Y are given integer constants.

Each possible location may be in view of some of Grundy's friends (namely, strictly within their triangular wedge of vision).

Grundy would like to know in how many different spots he can stand such that he will be in view of at most i of his friends, for every possible value of i from 0 to N.

Input Specification

The first line of input contains the integer N (1 \le N \le 100\,000).

The next line contains three integers: L, R, and Y (-1\,000\,000\,000 \le L \le R \le 1\,000\,000\,000, 1 \le Y \le 1\,000\,000).

Each of the next N lines contain three integers: the i-th such line contains x_i (L \le x_i \le R), the x-value of the position of friend i followed by two integers v_i and h_i (1 \le v_i, h_i \le 100). The slopes v_i/h_i and -v_i/h_i define the triangular wedge of vision for friend i.

For 15 of the 25 marks available, -1\,000\,000 \le L \le R \le 1\,000\,000.

Output Specification

The output is N+1 lines, where each line i (0 \le i \le N) contains the integer number of positions in which Grundy can stand and be in view of at most i of his friends.

Sample Input

-7 7 3
0 2 3
-4 2 1
3 3 1

Sample Output


Explanation of Output for Sample Input

There are three friends with the following triangular wedges of vision, along with the possible positions that Grundy can be placed, as shown in the diagram below:

Notice the points (2, 3) and (4, 3) are visible only by the friend at position 0, since they lie on the boundary of the triangular wedge of vision for the friend at position 3.


There are no comments at the moment.