All submissions for this problem are available.
Read problems statements in Mandarin Chinese, Russian and Vietnamese as well.
Chef prepares the following problem for a programming contest:
You are given N points with integer coordinates (-1000 ≤ xi, yi ≤ 1000). No two points collide and no three points are collinear. For each of the 2N-1 non-empty subsets of points, find the size (the number of points) of its convex hull. Print the sum of those sizes.
Chef has already prepared some tests for his problem, including a test with the maximum possible answer. He now needs a test with a quite small answer (but not necessarily the minimum possible one). For given N, your task is to find any valid set of N points for which the answer doesn't exceed 4 * 1015 (4,000,000,000,000,000).
The only line of the input contains a single integer N, denoting the number of points.
Print exactly N lines. The i-th line should contain two integers xi and yi, denoting coordinates of the i-th point.
The printed set of points must satisfy all the given conditions. At least one such set exists for every N allowed by the constraints given below.
Note: Remember that you don't print N in the first line.
- 2 ≤ N ≤ 50
Input: 5 Output: -150 150 150 150 -150 -150 150 -150 11 13
Let's analyze sizes of convex hulls for the provided output. There are 25-1 non-empty sets of points.
- There are 5 sets of points that consist of only 1 point each. The convex hull of each of those sets has size 1.
- Similarly, 10 sets of points consist of 2 points each, and the size of each of their convex hulls is 2.
- Similarly, there are 10 sets with 3 points each, and the size of each of their convex hulls is 3.
- The set with points (-150, -150), (-150, 150), (150, 150), (11, 13) has a convex hull of size 3. You can note that the point (11, 13) is inside the triangle formed by the other three points.
- The set with points (-150, 150), (150, 150), (150, -150), (11, 13) has a convex hull of size 3 as well.
- There are 3 other sets with 4 points, and for each of them the convex hull has size 4.
- Finally, the set with all 5 points has a convex hull of size 4.
The sum of sizes of convex hulls is (5 * 1) + (10 * 2) + (10 * 3) + 3 + 3 + (3 * 4) + 4 = 5 + 20 + 30 + 6 + 12 + 4 = 77, which obviously doesn't exceed 4 * 1015.
|Time Limit:||1 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.