Points Inside A Polygon
All submissions for this problem are available.
Read problems statements in Mandarin chinese, Russian and Vietnamese as well.
You are given a convex polygon with N vertices.
You have to find any ⌊N/10⌋ distinct points with integer coordinates that lie strictly inside the polygon, or determine that such a set of points doesn't exist.
Note: ⌊⌋ denotes the floor function, typically used in integer division.
- The first line of the input contains a single integer T denoting the number of test cases. The description of T test cases follows.
- The first line of each test case contains a single integer N denoting the number of vertices of the polygon.
- The following N lines describe the vertices of the polygon in anticlockwise order. Each of these lines contains two space-separated integers x and y denoting the coordinates of one vertex.
For each test case, if a valid set of points doesn't exist, print a single line containing the integer -1. Otherwise, print ⌊N/10⌋ lines. Each of these lines should contain two space-separated integers denoting the coordinates of one point.
The coordinates of all points should be integers with absolute value not exceeding 109. If there are multiple solutions, you may print any one.
- 1 ≤ T ≤ 105
- 10 ≤ N ≤ 105
- sum of N over all test cases ≤ 5 · 105
- |x|, |y| ≤ 109
- no three vertices of the polygon will be collinear
Subtask #1 (30 points): 1 ≤ T ≤ 100, 10 ≤ N ≤ 100
Subtask #2 (70 points): original constraints
Input 1 11 0 0 1 1 2 3 2 5 0 10 -2 10 -5 9 -8 7 -8 4 -6 1 -2 0 Output 0 1
Example case 1: The polygon is shown in the picture:
You are required to output exactly ⌊N/10⌋ = ⌊11/10⌋ = 1 point.
One possible point that you can output is (0, 1). You can also output (0, 2), (-1, 3) or (1, 3).
However, (0, 0) is a wrong answer, because this point lies on the border of the convex polygon.
If you output (-1, -1), that's also a wrong answer, because this point lies outside the convex polygon. You can't output (1.1, 1.5) either, because it doesn't have integer coordinates, though it lies strictly inside the polygon.
|Tags||admin2, constructive, convex-polygon, feb18, medium|
|Time Limit:||2 sec|
|Source Limit:||50000 Bytes|
|Languages:||C, CPP14, JAVA, PYTH, PYTH 3.6, PYPY, CS2, PAS fpc, PAS gpc, RUBY, PHP, GO, NODEJS, HASK, rust, SCALA, swift, 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, kotlin, PERL6, TEXT, SCM chicken, PYP3, CLOJ, COB, FS|
Fetching successful submissions
If you are still having problems, see a sample solution here.