All Tracks Math Problem

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

enter image description here

  • \(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++, C++14, Clojure, C#, D, Erlang, F#, Go, Groovy, Haskell, Java, Java 8, JavaScript(Rhino), JavaScript(Node.js), Julia, Kotlin, Lisp, Lisp (SBCL), Lua, Objective-C, OCaml, Octave, Pascal, Perl, PHP, Python, Python 3, R(RScript), Racket, Ruby, Rust, Scala, Swift, Visual Basic

CODE EDITOR

Initializing Code Editor...
Your Rating:

Contributor

This Problem was Asked in

HackerEarth

Challenge Name

HackerEarth Collegiate Cup Second Elimination

OTHER PROBLEMS OF THIS CHALLENGE
Notifications
View All Notifications

?