0076. Mushroom Pizza

Имя входного файла:	pizza.in
Имя выходного файла:	pizza.out
Ограничение по времени:	3 s
Ограничение по памяти:	64 megabytes

You have a mushroom pizza. You want to divide it into m equal pieces in such a manner: the difference between the number of mushrooms in the piece having most mushrooms and in the piece having least mushrooms is minimal.

Pizza is a circle. The pieces are sectors of a circle.

Input file

First line of input file contains three integer numbers n, m and r (1 ≤ n ≤ 1000, 2 ≤ m ≤ 1000, 1 ≤ r ≤ 10000). n lines follow, each containing 2 integers x_i and y_i – coordinates of mushrooms. The mushrooms are strictly inside the pizza (the circle with radius r and center at (0,0)). No mushroom occupies the center of a pizza (i.e. for every i either x_i ≠ 0 or y_i ≠ 0).

The cut between pieces cannot go through any mushroom.

Output file

On the first line of output file output the difference of the number of mushrooms beetween pieces having most and least number of mushrooms (i.e. the value of function you minimise).

On the second line, output coordinates of any point with integer coordinates on any piece-cutting ray. The coordinates should be less than 2³¹ in absolute value.

Examples:

pizza.in	pizza.out
4 4 2 1 1 -1 1 -1 -1 1 -1	0 0 1

Источник: Petrozavodsk Winter 2003. Our Special Contest on Geometry, Wednesday, February 05
Автор: Andrew Lopatin, Nick Durov

Обсудить       Отправить решение



Версия для печати