All submissions for this problem are available.
Bitcity has two large (disjoint) playgrounds, named, quite appropriately, Ground 0 and Ground 1. Naturally, bitzens like convexity, and both these playgrounds are convex polygons.
It's evening and lots of bitkids are playing on these grounds, some on ground 0, some on ground 1. There are also some bitguards watching over the bitkids. The bitguards are standing on vertices of the playground.
You have access to the location (x-y coordinates) of N bitzens, which includes ALL the bitguards and some (may be none!) of the bitkids, along with the playground that they are in. However, your system is unable to differentiate between bitguards, and bitkids; it just sees coordinates and playground number.
Now, you get more coordinates for Q new bitzens, and must ascertain whether each of the bitzens is in Ground 0, or Ground 1.
There is single test case.
- First line contains a single integer, N.
- N lines follow, each containing 3 space separated numbers : 2 real numbers (C++ float) denoting x and y, and a third number, 0 or 1, denoting the playground number. These are the coordinates of the bitzens whose playground you know.
- Then follows a line containing a single integer, Q.
- Q lines follow, each containing 2 space separated real numbers (C++ float) denoting x and y. These are your queries.
Note : Be careful while reading inputs as there are very large number of inputs.
Note : There is a stringent time-limit for this problem. Be careful.
Output Q lines, each containing 0 or 1, the answer for the corresponding query coordinate.
- N ≤ 10^5
- Q ≤ 4*10^5
- 10^(-7) ≤ x, y ≤ 10^7
- All x and y coordinates will be specified to the third decimal point.
Input: 8 0.000 1.000 0 1.000 0.000 0 1.000 1.000 0 0.700 0.700 0 0.000 -1.000 1 -1.000 0.000 1 -1.000 -1.000 1 -0.700 -0.700 1 3 0.600 0.600 -0.600 -0.600 0.800 0.800 Output: 0 1 0
|Time Limit:||0.5 - 2 sec|
|Source Limit:||50000 Bytes|
|Languages:||C, CPP14, JAVA, PYTH, PYTH 3.5, PYPY, CS2, PAS fpc, PAS gpc, RUBY, PHP, GO, NODEJS, HASK, SCALA, D, PERL, FORT, WSPC, ADA, CAML, ICK, BF, ASM, CLPS, PRLG, ICON, SCM qobi, PIKE, ST, NICE, LUA, BASH, NEM, LISP sbcl, LISP clisp, SCM guile, JS, ERL, TCL, PERL6, TEXT, SCM chicken, CLOJ, FS|
Fetching successful submissions
If you are still having problems, see a sample solution here.