Information

Deadline No deadline
Submission limit No limitation

Sign in

Geometry - Problem: Align polygon

In this problem you are going to practice rotations with a problem that appears sometimes a sub-routine of more complex problems.


Align Polygon

Given as input a polygon defined by \(n\) vertcies \(p_1, p_2, \ldots, p_n\) your task is to transform it with a translation and a rotation so that:

  1. The point \(p_1\) becomes the origin \((0, 0)\)
  2. The segment \(\overline{p_1 p_2}\) becomes thealigned with the x-axis in a way that \(p_2\) becomes the point \((d, 0)\) where \(d\) is the distance between \(p_1\) and \(p_2\).

The first sample input is illustrated in the following image.


geometry-alignpolygon/alignPolygon.png

Input

  • One line with a single integer \(n\) giving the number of vertices in the polygon.
  • \(n\) lines each with two integers \(x\) and \(y\) giving the the coordinates of those vertices. The vertices are given in counterclockwise order.

Constraints

  • \(3 \leq n \leq 1000\)
  • \(-10^5 \leq x, y \leq 10^5\)

Output

  • \(n\) lines each with two integers \(x\) and \(y\) giving the the coordinates the resulting polygon.

The will be accepted as long as it is accurate up to $10^{-6}$ relative or absolute precision.

Sample Test Cases

Sample input 1

Sample output 1

Sample input 2

Sample output 2


Max file size: 1.0 MiB
Allowed extensions: .java, .cpp, .py