|
Menu |
|
Задача Окружность
| Файл входного файла: | circle.in |
|---|---|
| Файл выходного файла: | circle.out |
| Ограничение по памяти: | 64 MB |
| Ограничение по времени: | 2 s |
Описание
На окружности на равном расстоянии друг от друга отмечены N точек, пронумерованных против часовой стрелки целыми числами от 1 до N. Вам даны несколько пар хорд этой окружности, концами которых являются данные точки. Для каждой пары хорд определите, пересекаются ли они(касание необходимо считать пересечением).
Формат входных данных
На первой строке входного файла расположены два целых числа: N и K (1 <= N <= 109, 1 <= K <=100). На следующих K строках расположены по 4 целых числа: A 1 , B 1 , A 2 , B 2 – номера концов первой хорды (A 1 , B 1 ) и второй хорды (A 2 , B 2 ). Числа в строках разделены пробелами.
Формат выходных данных
Для каждой пары хорд из входного файла выведите одну строку, содержащую YES, если диагонали пересекаются и NO, если они не пересекаются.
Примеры:
| ввод | вывод |
|---|---|
|
4 3
|
YES
|
|
|
|
Difficulty: 0.719844357977
Accepted: 8
Submitted: 16
Источник задачи: Республиканская олимпиада по информатике 2008–2009, Этап 2, Тур 1
Обсуждение:
Начать обсуждение:
Powered by django, eJudge.
Во-первых, будем считать, что A1 < B1 и A2 < B2 (если это не так, то добьемся этого поменяв числа в соответствующей паре местами). Далее, нарисовав один-два случая можно заметить, что хорды будут пересекаться или касаться только в трех случаях: * они совпадают, то есть обе вершины общие: ((A1 == A2) && (B1 == B2)) * одна вершина общая: ((A1 == A2) || (A1 == B2) || (A2 == B1) || (A2 == B2)) * вершины разные, и для каждой хорды выполняется следующее условие: если окружность разрезать по этой хорде, то вершины другой хорды должны быть в разных частях окружности: ((A1 < A2) && (A2 < B1) != (A1 < B2) && (B2 < B1)) Все решение заключается в проверке этих трех условий.!!!!!!!!!!! Кто не решит тот мещок!!!!!!!=)))xDDDDDDDD!
Дата: 2010-04-01 03:34
Ответить →
это в разборы надо. жми "Analyze this".
Дата: 2010-04-01 08:27
Ответить →