Chef and Polygons
All submissions for this problem are available.
Read problems statements in Mandarin Chinese and Russian.
Chef has N simple polygons (non self intersecting polygons) in which no two of them intersect with each other. For any two polygons P1, P2, either P1 lies inside P2 or vice versa.
Chef wants you to count number of polygons lying strictly inside each of the polygons.
First line of the input contains an integer T denoting the number of test cases. First line of each test case contains a single integer N denoting the number of polygons.
The description of N polygons is as follows:
- The first line contains an integer Mi denoting the number of vertices in the ith polygon
- The second line contains Mi pairs of integers Xi, j, Yi, j representing coordinates of vertices of ith polygon in clockwise or counterclockwise order
For each test case, output a single line containing N space-separated integers such that ith of them represents number of polygons lying inside the ith polygon.
- 1 ≤ T ≤ 105
- 2 ≤ N ≤ 105
- 3 ≤ Mi ≤ 105
- The sum of Mi (or total amount of given points) over all test cases in one test file does not exceed 2*105
- Absolute value of each coordinate doesn't exceed 109
Subtask 1: (10 points)
- T ≤ 6
- 2 ≤ N ≤ 10
- 3 ≤ Mi ≤ 10
- Absolute value of each coordinate doesn't exceed 30
Subtask 2: (20 points)
- All polygons are convex polygons .
Subtask 3: (70 points)
- Original constraints
Input: 1 3 6 -2 2 -1 1 2 2 2 -1 1 -2 -2 -2 3 -1 -1 1 -1 1 1 4 3 3 -3 3 -3 -3 3 -3 Output: 1 0 2
In the picture the first polygon is marked in green, second - in red and third in blue color.
|Tags||antoniuk1, cakewalk, geometry, june15, sorting|
|Time Limit:||1 sec|
|Source Limit:||50000 Bytes|
|Languages:||C, CPP14, JAVA, PYTH, PYTH 3.6, 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.