| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 4 초 | 1024 MB | 1 | 0 | 0 | 0.000% |
Из лечебницы Аркхем сбежали несколько особо опасных пациентов. Сейчас они находятся во внутреннем дворе лечебницы, который может быть представлен в виде квадратной части плоскости, содержащей все точки с координатами, по модулю не превышающими 10ドル^9$. Внутренний двор по периметру ограничен лечебницей, поэтому пациенты не могут вырваться наружу. Но персонал переживает, что они могут нанести увечья друг другу. Для того чтобы этого избежать, персонал может использовать специальную охранную систему, которая умеет строить бесконечные прямые стены, через которые пациенты не смогут перебраться. Использовать охранную систему дорого, поэтому персонал хочет построить минимальное количество стен, чтобы ни одна пара пациентов не могла добраться друг до друга. Помогите персоналу выбрать минимальное количество стен, которые удовлетворяют этим условиям.
Размерами пациентов и толщиной стен можно пренебречь, поэтому каждый пациент может быть представлен точкой с целыми координатами $x_i,ドル $y_i$ ($|x_i|, |y_i| \le 1,000円$), а стенам соответствуют прямые на плоскости. Для строительства стены охранной системе нужно сообщить две различные точки с целыми координатами $(x_1, y_1)$ и $(x_2, y_2),ドル находящиеся на территории внутреннего двора, и лежащие на прямой, соответствующей желаемой стене ($|x_1|, |y_1|, |x_2|, |y_2| \le 10^9$). При этом нельзя строить стену, содержащую точку, соответствующую одному из пациентов.
В первой строке дано одно целое число $n$ --- количество пациентов (1ドル \le n \le 12$). В следующих $n$ строках дано по два целых числа $x_i$ и $y_i$ --- координаты точки, в которой находится $i$-й пациент ($|x_i|, |y_i| \le 1,000円$). Гарантируется, что никакие две точки не совпадают.
В первой строке выведите одно целое число $m$ --- минимальное количество стен, которые необходимо построить.
В следующих $m$ строках выведите по четыре целых числа $x_{j, 1},ドル $y_{j, 1},ドル $x_{j, 2}$ и $y_{j, 2}$ --- координаты двух различных точек $(x_{j, 1}, y_{j, 1})$ и $(x_{j, 2}, y_{j, 2}),ドル через которые должна проходить $j$-я стена ($|x_{j, 1}|, |y_{j, 1}|, |x_{j, 2}|, |y_{j, 2}| \le 10^9$). Прямые, соответствующие стенам, не должны содержать точки, соответствующие пациентам. Вы можете вывести любой ответ, содержащий минимальное возможное количество стен.
2 0 0 1 1
1 1 0 0 1
4 -1 -1 1 1 -1 1 1 -1
2 0 -1 0 1 -1 0 1 0
4 0 0 1 0 3 0 7 0
3 0 1 1 -1 1 1 2 -1 3 1 4 -1
1 5 -3
0
Рис. 1:Пояснение к тестам
Зеленым отмечены позиции пациентов, рыжим --- стены и точки, через которые они проходят.