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++, 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...
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