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

Ural Regional School Programming Contest 2011

About     Problems     Submit solution     Judge status     Standings
Contest is over

K. Ent's Birthday

Time limit: 0.5 second
Memory limit: 64 MB
Problem illustration
Ent Fedya's birthday was coming up, and his friends made a birthday cake for him. They didn't know how many candles they should put on the cake because nobody remembered Fedya's age. That is why they just put a very large number of candles on the cake. When Ent Sasha saw the cake, he got angry because he had a very good memory and knew that Fedya would become k years of age. Happily, there were n > k candles on the cake. Since Fedya's age became known, the ents decided to cut from the cake a convex polygonal piece of nonzero area that would contain exactly k candles (counting the cakes inside the piece and on its boundary).
The cake is a 2 · 109 × 2 · 109 mm square. The distance from each candle to each side of the square is a positive integer number of millimeters.


The first line contains the integers n and k (1 ≤ k < n ≤ 1 000). In the following n lines you are given pairs of integers, which are the coordinates of the candles. The origin of coordinates is at the center of the cake and the coordinate axes are parallel to its sides. All the coordinates are strictly less than 109 in absolute value. It is guaranteed that no two candles are at the same point.


In the first line output the number m of vertices of the polygon that should be cut from the cake (3 ≤ m ≤ 10 000). In the following m lines give the coordinates of the vertices ordered counterclockwise. The coordinates must be integers not exceeding 109 in absolute value. The angles at the vertices must not be straight. The lengths of all sides must be positive. If there are several solutions, output any of them. It is guaranteed that there exists at least one solution satisfying the above constraints.


5 3
1 0
1 2
2 1
3 0
3 2
1 0
2 1
1 2
Problem Author: Denis Mukhametianov
Problem Source: Ural Regional School Programming Contest 2011
To submit the solution for this problem go to the Problem set: 1883. Ent's Birthday