Rotation in 2D Space

Problem #85

Tags: geometry popular-algorithm practical

Who solved this?

Let's practice the geometry programming of rotations. Such functionality is quite popular in graphic editors, but it is not the only use.

For example here is the widget Sphere Tag Cloud which can be used in creating funny design of the web-page. Dragging the mouse over the cloud you should see it scrolling like a globe. The effect is achieved by performing just two rotations around two axes (for each of floating element).

We'll start with something simpler. Suggest we have a planar map with points on it. For example it could be the picture of a sky with stars shining.

The task is to perform rotation of the map by the given angle. Round the resulting coordinates to nearest integer.

To check the result please output the names of stars sorted by Y coordinate and then by X (if the Ys are equal).

Input data contain the number of stars N and the rotation angle A (counterclockwise, from 0 to 360 degrees).
Next lines will contain data about one star each in form Name X Y. Coordnates would be integer, not exceeding 1000 in absolute value.
Answer should give the names of stars sorted by Y and then by X after rotation (and rounding).

Note: sorting should be performed in ascending order, i.e. from smallest values to largest.


input data:
4 45
Deneb -10 10
Algol 10 10
Sirius -10 -10
Mira 10 -10

Sirius Deneb Mira Algol

You may see schematic diagram of such rotation on the picture above. Here Sirius is green, Deneb is red, Mira is yellow and Algol is blue.

You need to login to get test data and submit solution.