| Вопрос: Олимпиада х.з. Задача 2 | Добавлено: 29.12.03 06:33 |
Автор вопроса:  Павел | Web-сайт: www.vbnet.ru | ICQ: 326066673 |
|
Задача 2 с какой-то олимпиады. 30 баллов из 200. N точек плоскости, не лежащие на одной прямой, заданы координатами. Требуется найти 3 таких точки из заданных, что треугольник с вершинами в этих точках не содержит ни одной точки из оставшихся 3<=N<=1000. Входные данные: в первой строке входного файла Input.txt указано число N. В последующих N строках содержатся пары вещественных чисел (читай, Double или Single) x, y - координаты точек, числа в строках отделены друг от друга пробелами. Выходные данные: выходной файл Output.txt должен содержать 3 строки. В каждой строке - по 2 числа - координаты вершин искомого треугольника. Пример Input.txt: 5 0 0 1 0 -1 0 0 1 0.2 0.2 Пример Output.txt: 0 0 -1 0 0 1 Хотелось бы посмотреть другие варианты решения (отличные от моего). Пишите. (Свой вариант попозже напишу). |
| Ответы | Всего ответов: 2 |
|
Номер ответа: 1 Автор ответа:  Neco ICQ: 247906854 Вопросов: 133 Ответов: 882 |
Web-сайт: Профиль | | #1 | Добавлено: 03.01.04 00:50 |
|
Муторно эту задачу решать на практике, но на олимпиаде я сделал бы так (первое, что в голову приходит): 1. берём точку 2. берём вторую 3. проверяем все точки (остальные) на принадлежность к этой прямой на данном участке. Делаем так: а) находим угловой коэф-т: арктангенс игрека к иксу. б) находим "приподнятость" (слагаемое b в формуле kx+b): в известном нам иксе находим kx. разница и есть b. зная всю эту хренотень на учаске от х1 до х2 проверяем принадлежность (подставляем в нашу прямую координаты точки если её икс лежит между нашими). Если 0, то точка на прямой. 4. на этом шаге можно сделать и иначе, но я сделал бы так: находим все отрезки, удовлетворяющие нашему условию и смотрим: никто из них не похож ли на треугольник. Т.е. сначала находим пару отрезков с общим концом, потом ищем отрезок с началом первого и концом второго. вот собственно и всё! Давай уже пиши своё решение. Я так понимаю здесь нужно использовать какое-нибудь малоизвестное правило (олимпиада ведь), но ничего гениального мне в башку не лезет - сплошная проза... |
||
|
Номер ответа: 2 Автор ответа:  Sharp Лидер форума ICQ: 216865379 Вопросов: 106 Ответов: 9979 |
Web-сайт: Профиль | | #2 | Добавлено: 03.01.04 06:23 |
|
Мне кажется, что это решается гораздо проще и достаточно строго. Берем любые две точки, потом перебираем все оставшиеся в поисках МИНИМУМА ПЛОЩАДИ ОБРАЗОВАННОГО ТРЕУГОЛЬНИКА, по формуле Герона. Очевидно, что если треугольник содержит точку, то треугольник с этой точкой и двумя другими будет меньше по площади, чем предыдущий... |
||
Страница: 1 |