Courtney and convex polygon
Tag(s):

## Hard, Math

Problem
Editorial
Analytics

Courtney has a convex polygon with $n$ vertices. She define the point with coordinates $x$ and $y$ as $(x, y)$. Courtney wants to do three types of queries:

• $1$ $x$ $y$ - rotate polygon on 90 degrees in counterclockwise order around point $(x, y)$
• $2$ $x$ $y$ - reflect polygon through point $(x, y)$
• $3$ $x$ $y$ - check if point $(x, y)$ is inside polygon

But it's too difficult for Courtney. Help her!

$INPUT$
The first line of input contains two integers $n$ and $q$ $(3 \leq n \leq 100 000, 1 \leq q \leq 300 000)$ - number of vertices in polygon and number of queries.

Then n lines follow. The $i$-th of these lines contains two integers $x_i$ and $y_i$ $(-100 000 000 \leq x_i, y_i \leq 100000000)$ - the i-th point of polygon. Points are given in counterclockwise order. There no such three points that would lie on the same polygon side. The area of polygon is greater than $0$.

Then $q$ lines follow. The $i$-th of these lines contains three integers $type_i$, $x_i$, $y_i$ $(1 \leq type_i \leq 3, -100000000 <= x_i, y_i <= 100000000)$ - parameters of $i$-th query.

$OUTPUT$
For each query of the third type print "Yes" (without quoters) if point $(x_i, y_i)$ lies in polygon and "No" (without quoters) otherwise.

$NOTES$
In this problem point lies inside polygon if it lies strictly inside polygon or lies on polygon border.

SAMPLE INPUT
3 8
3 0
0 4
-2 -2
3 3 0
3 -2 2
2 0 1
3 3 0
3 -2 2
1 2 0
3 1 -3
3 0 0

SAMPLE OUTPUT
Yes
No
No
Yes
Yes
No

Explanation

• $ABC$ - is polygon before changes
• $EFG$ - is $ABC$ after reflect it through $D$
• $IKJ$ - is $EFG$ after rotate it on 90 degrees in counterclockwise order around $H$
Time Limit: 1.0 sec(s) for each input file.
Memory Limit: 256 MB
Source Limit: 1024 KB
Marking Scheme: Marks are awarded when all the testcases pass.
Allowed Languages: C, C++, Clojure, C#, D, Erlang, F#, Go, Groovy, Haskell, Java, Java 8, JavaScript(Rhino), JavaScript(Node.js), Lisp, Lisp (SBCL), Lua, Objective-C, OCaml, Octave, Pascal, Perl, PHP, Python, Python 3, R(RScript), Racket, Ruby, Rust, Scala, Scala 2.11.8, Swift, Visual Basic

## CODE EDITOR

Initializing Code Editor...

## This Problem was Asked in

Challenge Name

HackerEarth Collegiate Cup Second Elimination

OTHER PROBLEMS OF THIS CHALLENGE
• Data Structures > Advanced Data Structures
• Math > Number Theory
• Algorithms > Sorting
• Data Structures > Advanced Data Structures
• Algorithms > Graphs
• Data Structures > Advanced Data Structures
• Algorithms > String Algorithms
• Algorithms > Graphs