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

Tetrahedron Team Programming Contest May 2001

About     Problems     Submit solution     Judge status     Standings
Contest is over

D. Pencils and Circles

Time limit: 1.0 second
Memory limit: 64 MB
One old man and one old woman sit at the table and write letters. On the table in front of them at the coordinates (xi, yi) stay N pencils. Diameter of pencils is 0 and all of them stay vertically. Man and woman decide to divide pencils into two equal groups. In order to do this old man give thread and put it on the table so that thread lay in a circle. Circle must cross over three pencils. He wants one group to get into the circle and other group not to get into the circle.


At the first line of the input is one odd integer 3 ≤ N ≤ 5000. At the next N lines are coordinates of pencils. There are no three pencils staying in one line and there are no four pencils staying on one circle. All coordinates are integers that are not greater than 108 by absolute value.


You must output 6 integers — coordinates of three pencils over which cross thread. Inside of circle must be (N−3)/2 pencils. On the circle must be these three pencils. And outside of the circle must be others (N−3)/2 pencils. If there is no solution you must output "No solution". If there are more than one solution output any of them.


0 0
1 0
2 -1
2 1
1 1
0 2
-3 -1
0 0
1 0
2 1
Problem Author: Katya Ovechkina
Problem Source: Tetrahedron Team Contest May 2001
To submit the solution for this problem go to the Problem set: 1103. Pencils and Circles