Protecting Three People
Time limit2sMemory limit128 MB
Given a simple polygon with up to 10,000 vertices, determine for three query points whether each lies inside or on the polygon's boundary.
- Level
Medium5 of 10
- Topics
- Geometry, Math, Implementation
- Solved
- No attempts yet
Problem
Wooseok wants to protect Daeyeon, Younghoon, and Beomjin with a polygon-shaped shield. The vertices of the shield and the three people's positions are given.
A person is considered protected if their position is inside the shield or on its boundary. Determine, in input order, whether each of the three people is protected.
Input
The first line contains the number of shield vertices N(3 ≤ N ≤ 10,000).
Each of the next N lines contains the coordinates of one shield vertex in order. The vertices may be given clockwise or counterclockwise.
The next three lines contain the coordinates of Daeyeon, Younghoon, and Beomjin, in that order.
Every coordinate is an integer between 0 and 1,000,000,000, inclusive.
Output
Print three lines. For each person in input order, print 1 if they are protected, and 0 otherwise.