Willian is traveling in Kazakhstan to take a break from work and college, exhausted from handling numerous server issues at his company. One night, he decided to leave the hotel to enjoy the area and appreciate the beautiful local scenery, visiting landmarks such as the Baiterek Tower, the Hazrat Sultan Mosque, and other places. As he looked up at the sky in front of the mosque, Willian noticed how it was filled with stars, framed by the illuminated minarets of the mosque. The stars twinkled and faded against the dark sky, while clouds passed over them in the darkness. That evening, Willian looked at the stars and, after studying so much geometry, doing numerous lists, and programming exercises, he wondered:
— Which pair of stars produces the largest absolute value of the slope if connected by a line?
A line can be algebraically described by linear equations such as $$$y = ax+b$$$, where $$$x$$$ is the independent variable of the function $$$y = f(x)$$$, the constant $$$a$$$ is the slope, and the constant $$$b$$$ is the $$$y$$$-intercept of the line. The absolute value is defined by a function $$$y = |x|$$$, where if $$$x \lt 0$$$, then $$$|x| = - x$$$, and if $$$x \geq 0$$$, then $$$|x| = x$$$.
Willian continued to enjoy the view of the sky and soon realized that the phenomenon of stars being covered by clouds could be represented as follows. Initially, there is a configuration of $$$N$$$ stars. After that, there are $$$Q$$$ events, where the events are characterized by:
In the initial configuration of the stars and after each of the events, we want to determine the largest absolute value of the slope among all pairs of stars.
The input consists of two integers $$$N$$$ and $$$Q$$$, followed by $$$N$$$ pairs of integers representing the coordinates of each star in the initial configuration. After that, there are $$$Q$$$ events described by three integers, where the first value defines the type of the event: if it is $$$1$$$, it is an insertion event, and if it is $$$2$$$, it is a removal event. The second and third values define the coordinates $$$X_i$$$ and $$$Y_i$$$. It is guaranteed that no two stars have the same y-coordinate or the same x-coordinate, meaning no two stars are on the same vertical or horizontal line. Furthermore, at the time of a star's removal, it is guaranteed that the star exists.
$$$0 \leq N + Q \leq 2 \cdot 10^5$$$
$$$1 \leq X_i, Y_i \leq 10^9$$$
Print $$$Q + 1$$$ lines each showing the largest absolute value of the slope. The first line is the result for the initial configuration, and the following $$$Q$$$ lines show the updated result after each event is processed.
For each case, print two integers $$$A$$$ and $$$B$$$ that represent the largest absolute value of the slope as an irreducible fraction $$$\frac{A}{B}$$$, where $$$gcd(A, B) = 1$$$ (with $$$gcd$$$ being the greatest common divisor function). If no pair of stars exists, print $$$-1$$$.
2 32 23 31 1 41 4 12 1 4
1 1 2 1 2 1 2 1
0 0
-1
| 2024 USP Try-outs |
|---|
| Finished |
