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.
Input
 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 spaceseparated integers x and y denoting the coordinates of one vertex.
Output
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 spaceseparated integers denoting the coordinates of one point.
The coordinates of all points should be integers with absolute value not exceeding 10^{9}. If there are multiple solutions, you may print any one.
Constraints
 1 ≤ T ≤ 10^{5}
 10 ≤ N ≤ 10^{5}
 sum of N over all test cases ≤ 5 · 10^{5}
 x, y ≤ 10^{9}
 no three vertices of the polygon will be collinear
Subtasks
Subtask #1 (30 points): 1 ≤ T ≤ 100, 10 ≤ N ≤ 100
Subtask #2 (70 points): original constraints
Example
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
Explanation
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.
Author:  admin2 
Tester:  r_64 
Editorial  https://discuss.codechef.com/problems/POINPOLY 
Tags  admin2, constructive, convexpolygon, feb18, medium 
Date Added:  24012018 
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 
Comments
 Please login at the top to post a comment.
SUCCESSFUL SUBMISSIONS
Fetching successful submissions
HELP
If you are still having problems, see a sample solution here. 