ENG  RUSTimus Online Judge
Online Judge
Online contests
About Online Judge
Frequently asked questions
Site news
Problem set
Submit solution
Judge status
Update your info
Authors ranklist
Current contest
Scheduled contests
Past contests

NEERC, Eastern subregion, Yekaterinburg, October 2006

About     Problems     Submit solution     Judge status     Standings
Contest is over

E. Good Manners

Time limit: 1.5 second
Memory limit: 64 MB
Although Vovan is a New Russian, he tries to learn good manners. His new image-maker teaches Vovan that a well-bred person would choose from several cake pieces on a table either the smallest or the nearest one. Vovan wants to appear a well-bred person at his oncoming birthday, but he also wants to get a big piece of cake. Fortunately, as a host, Vovan can himself seat his guests at his big round table. Help Vovan to choose a place at the table such that the piece of cake nearest to him is as big as possible.


The first line contains two integers that are the radius of the table R in meters and the number K of cake pieces on the table (1 ≤ R ≤ 100, 2 ≤ K ≤ 1000). Each of the next K lines contains three numbers describing a piece of cake: its coordinates in meters and weight in grams (an integer from 1 to 10000). The center of the table is the coordinate origin. All the pieces have distinct coordinates and lie on a table.


Output the coordinates of a place at the table (a point on the table's circumference) such that in this place Vovan would get the biggest possible piece, at the same time looking as a well-bred person (if there are several pieces nearest to this point, then Vovan can take the biggest of them). Coordinates should be precise up to 7 digits.


10 3
1 -1 100
2 2 200
-2.5 -2.56 1
6 8
Problem Author: Stanislav Vasilyev
Problem Source: Quarter-Final of XXXI ACM ICPC - Yekaterinburg - 2006
To submit the solution for this problem go to the Problem set: 1504. Good Manners