#P3691. Danmaku Line Classification
Danmaku Line Classification
Danmaku Line Classification
In a 100×100 battle arena, two fairies, Sunny Milk and Lunar Child, fire bullets that almost completely fill the arena. These bullets can be perfectly separated by a fixed, non‐vertical line. All bullets above the line are sun bullets (fired by Sunny Milk), and all bullets below the line are moon bullets (fired by Lunar Child).
Due to intense battle, the enemy fairy, Cirno, may have misidentified the type of a bullet in extremely rare cases (at most 0.1% of the observations). Cirno has recorded the positions of all observed bullets along with their (possibly slightly erroneous) type identifications. Now, given some future positions where a bullet may appear, she wishes to know which type the bullet would be if it appears.
Your task is to determine, for each queried position, whether it falls in the sun region or the moon region.
Note: It is known that there exists a fixed line (of nonzero, finite slope) that exactly divides the battle arena into two regions such that almost all observed sun bullets lie on one side and almost all moon bullets on the other side. You can assume that the misidentification rate is extremely low.
inputFormat
The input begins with an integer N (N ≥ 4), the number of observed bullets.
Each of the following N lines contains three tokens: two floating-point numbers x and y (0 ≤ x, y ≤ 100) representing the bullet's position, and a string which is either sun
or moon
– indicating the type recorded for that bullet.
Then follows an integer Q (Q ≥ 1), the number of query positions. Each of the next Q lines contains two floating-point numbers x and y representing a query position.
outputFormat
For each query, output on a separate line a string: sun
if the bullet at that position would be a sun bullet, or moon
if it would be a moon bullet. In case the point lies exactly on the separating line, output sun
.
sample
4
10 90 sun
20 80 sun
30 10 moon
40 20 moon
3
15 85
35 15
25 50
sun
moon
sun
</p>