## CCO '20 P1 - A Game with Grundy

View as PDF

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

Author:
Problem type

Grundy is playing his favourite game — hide and seek.

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

Grundy may choose to hide at any location , where is an integer satisfying , and , , and 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 of his friends, for every possible value of from to .

#### Input Specification

The first line of input contains the integer .

The next line contains three integers: , , and , .

Each of the next lines contain three integers: the -th such line contains , the -value of the position of friend followed by two integers and . The slopes and define the triangular wedge of vision for friend .

For 15 of the 25 marks available, .

#### Output Specification

The output is lines, where each line contains the integer number of positions in which Grundy can stand and be in view of at most of his friends.

#### Sample Input

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

#### Sample Output

5
12
15
15

#### 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 and 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.