[solution] Four Equidistant Points on a Grid solution codechef

by

Four Equidistant Points on a Gridsolution codechef – The manhattan distance between two points P1(x1,y1)P1(x1,y1) and P2(x2,y2)P2(x2,y2) is given by d(P1,P2)=|x2−x1|+|y2−y1|d(P1,P2)=|x2−x1|+|y2−y1|.

In other words, manhattan distance is the minimum number of moves required to reach P2P2 from P1P1 if, in each move, you are allowed to travel one unit along the XX-axis or one unit along the YY-axis.

Four Equidistant Points on a Grid solution codechef

You are given an integer DD. Find four points (P1,P2,P3,P4)(P1,P2,P3,P4) with integer coordinates, such that:

  • The absolute value of both XX and YY coordinates of all points is at most 109109.
  • The manhattan distance between any pair of points is DD . More formally, d(Pi,Pj)=Dd(Pi,Pj)=D for all 1≤i<j≤41≤i<j≤4.

If such set of points do not exist, print -1. If there are multiple solutions, you may print any.

Note: It is guaranteed that whenever there exists a solution, there exists one in which all points have coordinates with absolute values not more than 109109.

Input Format

  • The first line contains a single integer, DD – as per the problem statement.

Four Equidistant Points on a Grid solution codechef

  • If there is no solution, print in a single line the integer -1.
  • Otherwise print 44 lines. The ithith line, should contain two space separated integers, XiYiXiYi, the coordinates of the point PiPi, such that 0≤|Xi|,|Yi|≤1090≤|Xi|,|Yi|≤109.

Constraints

  • 1≤D≤1051≤D≤105

Subtasks

Subtask #1 (100 points): original constraints

Sample Input 1 

2

Four Equidistant Points on a Grid solution codechef

 

0 1
1 2
2 3
3 4

Four Equidistant Points on a Grid Explanation

The following sample output for this testcase is not correct, but is only provided to clarify the output format

The points in the solution are P1(0,1),P2(1,2),P3(2,3)P1(0,1),P2(1,2),P3(2,3) and P4(3,4)P4(3,4). d(P1,P2)=|0−1|+|1−2|=2d(P1,P2)=|0−1|+|1−2|=2 but d(P1,P3)=|0−2|+|1−3|=4d(P1,P3)=|0−2|+|1−3|=4. As d(P1,P2)≠d(P1,P3)d(P1,P2)≠d(P1,P3), the solution is incorrect.

A correct solution will satisfy d(P1,P2)=d(P1,P3)=d(P1,P4)=d(P2,P3)=d(P2,P4)=d(P3,P4)d(P1,P2)=d(P1,P3)=d(P1,P4)=d(P2,P3)=d(P2,P4)=d(P3,P4).

A correct sample output is not provided so as to not reveal any hints about the solution.

Sample Input 2 

1

Sample Output 2 

-1

Explanation

You may verify that for D=1D=1, there are no set of points P1,P2,P3,P4P1,P2,P3,P4 as per the problem statement. This output is correct.

Leave a Comment