eolymp
bolt
Try our new interface for solving problems
Məsələlər

Футбол 2

Футбол 2

Zaman məhdudiyyəti 2 saniyə
Yaddaşı istafadə məhdudiyyəti 256 MiB

На футбольном поле размером x × y находятся n футболистов. Они уже очень устали и стоят на месте, но ждут, куда упадёт мяч, чтобы побежать к нему. Футболист бежит к мячу в том случае, если мяч упал к этому футболисту ближе, чем к любому другому футболисту.

Требуется определить для каждого футболиста границы зоны, при попадании в которую он побежит к мячу, если известно, что она представляет собой многоугольник.

Giriş verilənləri

В первой строке входного файла заданы три целых числа x, y и n (2x, y10^5, 1n30000). Следующие n строк содержат целые координаты футболистов x_iy_i (0 < x_i < x, 0 < y_i < y). Никакие два футболиста не стоят в одной точке.

Çıxış verilənləri

В выходной файл выведите n строк. В каждой из строк первое число - количество вершин зоны k_i, далее k_i чисел - координаты вершины x_ij y_ij в порядке обхода против часовой стрелки, начиная с самой нижней из самых левых вершин зоны. Вещественные числа выводите с максимальной точностью.

Nümunə

Giriş verilənləri #1
4 4 4
1 1
1 3
3 1
3 3
Çıxış verilənləri #1
4  0.00000000 0.00000000 2.00000000 0.00000000 2.00000000 2.00000000 0.00000000 2.00000000
4  0.00000000 2.00000000 2.00000000 2.00000000 2.00000000 4.00000000 0.00000000 4.00000000
4  2.00000000 0.00000000 4.00000000 0.00000000 4.00000000 2.00000000 2.00000000 2.00000000
4  2.00000000 2.00000000 4.00000000 2.00000000 4.00000000 4.00000000 2.00000000 4.00000000