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

Выпуклая оболочка решеточных точек

Выпуклая оболочка решеточных точек

Zaman məhdudiyyəti 1 saniyə
Yaddaşı istafadə məhdudiyyəti 64 MiB

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

Многоугольник называется выпуклым, если отрезок, соединяющий две любые его точки, лежит внутри (или на границе) многоугольника. Или то же самое, что каждый внутренний угол многоугольника меньше 180 градусов.

Множеством S решеточных точек выпуклой оболочкой называется наименьший выпуклый многоугольник (решеточный), который содержит в себе все точки множества. (Вершины выпуклой оболочки должны принадлежать множеству решеточных точек S). Если все точки лежат на одной прямой, то их выпуклой оболочкой будет отрезок (вырожденный многоугольник – как показано на самом правом рисунке). На рисунках ниже точки множества отмечены жирными точками, вершины выпуклой оболочки - обозначены X, а выпуклая оболочка отображена в виде отрезков, соединяющих ее вершины. Не все точки на выпуклой оболочке являются ее вершинами.

Вершины решеточного многоугольника находятся в стандартном порядке, если:

a) Первая вершина имеет наибольшую y координату. Если две вершины имеют одинаковую y координату, то первой считается та, у которой x меньше.

b) Вершины многоугольника задаются по часовой стрелке.

Напишите программу, которая читает множество решеточных точек и выводит вершины выпуклой оболочки в стандартном порядке.

Giriş verilənləri

Первая строка содержит единственное целое число P, (1P1000) - количество тестов. Первая строка каждого теста содержит его номер, пробел и количество точек N (3N50) во множестве. Далее задаются точки множества, не более 5 точек в каждой строке (последняя строка может содержать и меньше). Каждая точка задается двумя целыми числами, разделенными пробелом, описывающих ее x и y координату.

Çıxış verilənləri

Для каждого теста следует вывести несколько строк. Первая строка содержит номер теста и количество вершин в выпуклой оболочке. Далее следуют вершины выпуклой оболочки в стандартном порядке, по одной вершине в строке. Каждая строка содержит x и y координату вершины, разделенные пробелом.

Nümunə

Giriş verilənləri #1
4
1 25
2 1 7 1 1 2 9 2 1 3
10 3 1 4 10 4 1 5 10 5
2 6 10 6 2 7 9 7 3 8
8 8 4 9 7 9 6 2 3 3
5 4 7 5 8 6 4 6 3 7
2 30
3 9 6 9 3 8 9 8 3 7
12 7 2 6 12 6 2 5 12 5
2 4 12 4 1 3 11 3 1 2
11 2 1 1 11 1 1 0 10 0
4 -1 10 -1 7 -2 10 -2 5 0
7 3 4 5 6 8 3 1 2 6
3 3
3 1 2 2 1 3
4 6
1 3 19 1 4 2 2 1 11 2
10 1
Çıxış verilənləri #1
1 10
4 9
7 9
10 6
10 3
9 2
7 1
2 1
1 2
1 5
2 7
2 8
3 9
6 9
12 7
12 4
10 -2
7 -2
1 0
1 3
3 2
1 3
3 1
4 4
1 3
11 2
19 1
2 1