21037번 - Polygonal Query 다국어

Let S be a set of points on a 2-dimensional plane. Initially, S is an empty set. Let convexHull(S) be the subset of S, which is the vertices of the convex hull of S without any three collinear points.

There are Q queries, each of the either following type:

1. add(x, y) - Adding a point (x, y) to S. It is guaranteed that no two points share the same xcoordinate or the same y-coordinate.
2. findHeavy(x₁, y₁, x₂, y₂) - Point (x₁, y₁) and point (x₂, y₂) are guaranteed to be distinct points in convexHull(S). It is also guaranteed that this query is called when convexHull(S) contains at least three points. Suppose a robot is located at (x₁, y₁) and the robot wants to go to (x₂, y₂). He can only traverse between the edges of the convex hull of S. Let cw be the number of points in convexHull(S) traversed by the robot if the robot moves in clockwise direction, and ccw be the number of points in convexHull(S) traversed by the robot if the robot moves in counter-clockwise direction. If cw ≥ ccw, output "CW", otherwise output "CCW".

The first line contains an integer: Q (1 ≤ Q ≤ 100,000) denoting the number of queries. The next Q following lines, each contains three or five integers.

• If the i-th query is an add(x, y) query, then the i-th line will be: 0 x y (0 ≤ x, y ≤ 1,000,000).
• If the i-th query is a findHeavy(x₁, y₁, x₂, y₂) query, then the i-th line will be: 1 x₁ y₁ x₂ y₂ (0 ≤ x₁, y₁, x₂, y₂ ≤ 1,000,000).

For each findHeavy(x₁, y₁, x₂, y₂) query, output the answer of the query on its own line.