Points, Lines, Triangles and Graphs

All submissions for this problem are available.
You are given an integer $k$. You want to choose $n$ points on the plane and join some pairs of those points with line segments (let us call them edges), such that :  $n \lt 510$  Any two points are distinct  No three points are collinear  The points have nonnegative integer coordinates $\leq 10^9$.  No two edges (drawn line segments) intersect at a point which is not an endpoint of either edge.  The number of triangles in the figure is exactly $k$. Note : A triangle means a triple of points such that there is an edge between any two of them. It is guaranteed that it is possible to select a set of points and line segments satisfying the above conditions. ###Input:  The only line of the input contains $k$, the number of required triangles. ###Output:  In first line print two integers, $n$ and $m$, the number of chosen points and number of line segments (edges) drawn between them. They must satisfy $1 \leq n \lt 510$ and $0 \leq m \leq \frac{n(n1)}{2}$  $i^{\text{th}}$ of the next $n$ lines should contain two space separated integers, $x_i, y_i$ denoting the $i^{th}$ chosen point. The coordinates must be nonnegative and $\leq 10^9$, i.e. $0 \leq x_i, y_i \le 10^9$.  $i^{\text{th}}$ of the next $m$ lines should contain two integers $u_i$ and $v_i$, denoting a line segment connecting the $u_i^{th}$ chosen point and the $v_i^{th}$ chosen point. $ 1 \leq u_i, v_i \leq n$ should be satisfied. No edge should be printed more than once. If there are multiple solutions, you can print any of them. ###Constraints  $ 1 \leq k \leq 1500$ ###Sample Input: ``` 2 ``` ###Sample Output: ``` 4 5 0 0 0 1 1 0 1 1 1 2 1 3 2 3 2 4 3 4 ``` ###Explanation: The figure shows the configuration corresponding to the given output. It contains 4 points, and 5 edges. Clearly there are 2 triangles, as the input requires it to be. ![After second second](https://codechef_shared.s3.amazonaws.com/download/Images/TST18KGP/POLITR... =275x275)Author:  jtnydv25 
Editorial  https://discuss.codechef.com/problems/POLITRI 
Tags  jtnydv25 
Date Added:  12122018 
Time Limit:  1 sec 
Source Limit:  50000 Bytes 
Languages:  C, CPP14, JAVA, PYTH, PYTH 3.6, PYPY, kotlin 
Comments
 Please login at the top to post a comment.
SUCCESSFUL SUBMISSIONS
Fetching successful submissions