Zvijezda
레이팅 미적용의견: 0
Mirko and Slavko are spending their free time playing with polygons and watching a new season of The
Biggest Loser. Mirko recently drew a convex polygon with an even number of vertices \(N\). Slavko then
considered each pair of oposite sides (two sides are opposite if there are ^{N}
_{2} {−}} ^{sides} ^{between} ^{them),} ^{drew
straight lines that lie on those sides and colored them along with the part of the plane that lies between
them and contains the polygon. Finally, Mirko found a set of \(Q\) points and decided to challenge Slavko to
answer for each point whether it lies in the colored or uncolored part of the plane.
The new episode of The Biggest Loser is about to start and Slavko doesn’t have the time to answer
Mirko’s queries. Can you help him?
Subtask
Score
Constraints
1
20
\(1 \le N\), \(Q \le 2000\), \(T = 0\)
2
30
\(1 \le N\), \(Q \le 10^{5}\), \(T = 0\)
3
60
\(1 \le N\), \(Q \le 10^{5}\), \(T = 1\)
The first line contains an integer \(T\) which is used as a parameter for generating Mirko’s queries. This
number can be either 0 or 1.
The second line contains an even integer \(N\) from the task description.
Each of the next \(N\) lines contains two integers \(X@@RISE_MATH_BLOCK_0@@i\) (0 ≤|\(Xi\)|, |Y i| ≤\(10^{9}\)) which represent one of the
polygon’s vertices. You can assume that the vertices are given in the counter clockwise order and that no
three successive vertices are collinear.
The next line contains an integer \(Q\) from the task description.
Each of the next \(Q\) lines contains two integers \(A@@RISE_MATH_BLOCK_1@@i\) (0 ≤|\(Ai\)|, |\(Bi\)| ≤\(2 \cdot 10^{18}\)) which are used as
parameters for generating the point in the \(i-th\) of Mirko’s queries.
Let \(X@@RISE_MATH_BLOCK_2@@i\) = (\(A\)\(i\) ⊕(\(T \cdot X\)^{3}
{i}{1}{)} }^{i{⊕} }^{T{·}}^{3
{−}}^{))
where ⊕represents the bitwise xor operation.
The \(i-th\) line of output should contain the word "DA" (YES in Croatian) if the point from \(i-th\) of Mirko’s
queries lies in the colored part of the plane. Otherwise, the \(i-th\) line should contain the word "NE" (NO in
Croatian).
0
4
1 1
5 1
4 3
2 2
4
3 2
2 4
6 2
4 5DA
NE
DA
NE0
6
-1 -1
2 -1
3 3
2 4
1 4
-2 1
6
2 2
3 0
1 -6
2 6
-5 5
5 10DA
DA
NE
NE
NE
NE1
6
-1 -1
2 -1
3 3
2 4
1 4
-2 1
6
2 2
3 0
1 -6
2 6
-5 5
5 10DA
DA
DA
NE
NE
NEClarification of the second example:
Clarification of the third example: The colored parts of the plane are the same as in the second
example and the points in Mirko’s queries are: (2, 2), (2, 1), (9, −14), (25, 29), (−32, 30) and (30, 17).
평가 및 의견
Zvijezda
Log in to rate problems.
아직 의견이 없습니다. 자격이 된다면 위 양식에서 가장 먼저 평가해 보세요.
풀이 제출
Zvijezda