Здравствуйте, уважаемые знатоки =)
Есть такая задача: дано N точек, N <= 2000; нужно найти трегульник максимальной площади, вершинами которого есть 3 и тех N точек. (Точки уже образуют выпуклый многоугольник и заданы в порядке обхода).
У меня 90/100 баллов.(Решал перебором вершины, а остальные две — двумя указателями).
Хотелось бы услышать советы и желательно код.
P.S.: идея у меня вроде правильная, но вот руки... =D
→ Обратите внимание
→ Трансляции
→ Лидеры (рейтинг)
| № | Пользователь | Рейтинг |
|---|---|---|
| 1 | tourist | 3690 |
| 2 | jiangly | 3647 |
| 3 | Benq | 3581 |
| 4 | orzdevinwang | 3570 |
| 5 | Geothermal | 3569 |
| 5 | cnnfls_csy | 3569 |
| 7 | Radewoosh | 3509 |
| 8 | ecnerwala | 3486 |
| 9 | jqdai0815 | 3474 |
| 10 | gyh20 | 3447 |
| Страны | Города | Организации | Всё → |
→ Лидеры (вклад)
| № | Пользователь | Вклад |
|---|---|---|
| 1 | maomao90 | 174 |
| 2 | awoo | 164 |
| 3 | adamant | 162 |
| 4 | TheScrasse | 159 |
| 5 | nor | 157 |
| 6 | maroonrk | 156 |
| 7 | -is-this-fft- | 152 |
| 8 | orz | 146 |
| 9 | Petr | 145 |
| 9 | pajenegod | 145 |
→ Найти пользователя
→ Прямой эфир
Codeforces (c) Copyright 2010-2024 Михаил Мирзаянов
Соревнования по программированию 2.0
Время на сервере: 15.05.2024 21:33:39 (h2).
Десктопная версия, переключиться на мобильную.
При поддержке
Читаю заголовок — понимаю, что человеку интересно знать решение задачи или что-то уточнить. Читаю пост, и понимаю, что человек знает решение, да и к тому же рассказал его в посте. Дальше понимаю, что проблема в другом — в коде. А кода нет...
Так-то оно и есть)) Ищу человека, который писал подобное.
Ну ок. Но в посте просятся советы, дам один. Понятно как решать задачу за куб. И ошибиться там негде. Напиши стресс-тест.
Да у меня быдлокод, там что-то убери и все работать не будет :) Вот я и хочу чистую красивую реализацию увидеть. Этот метод(2 указателя) — вообще очень интересная тема.
N^2 * log(N) заходит?
Думаю, что да. Ты хочешь перебрать пару(вершини при основе), а потом тернарник запустить, чтоб 3-ую вершину найти(которая будет образовывать макс. высоту треугольника)?
да.
думал об этом... лень писать =D
Извиняюсь за оффтоп, но как вонимать вот это: 8568517, 8572637?
У меня был плохой день... =) Теперь я уже вырос и не делаю подобных вещей. Да и по правилам КФ ты не должен вылаживать свой код в интернет во время соренования(себя ты тоже спалил).
Интересно, куда же я его выложил?)
Интересно, откуда же я его взял?
Мне тоже это интересно)
pastebin.ru Ты выложил и не знаешь об этом? Может, ты сам его оттуда взял? =)
Боже, что ты несешь... Будь так добр предъявить пруф
И без пруфов понятно, что если у двух человек во время соревнования сдан одинаковый код — значит либо один дал свой код второму, либо им обоим дал код кто-то третий
либо первый выложил как public в ideone, а второй отловил
Может все-таки выкладывать?
Решение за квадрат. Совершенно очевидно, что все три точки лежат на выпуклой оболочке. Перебираем первую, вторую — в порядке обхода, два варианта третьей — указателями. Итого
Возможно, здесь же есть решение за
. Кажется, что вторую и третью точку можно подбирать тернарниками, если правильно разбить на отрезки (интуитивная оценка: расстояние до самой удаленной точки вдоль прямой выпукло относительно угла; площадь треугольника есть произведение двух таких расстояний и тоже выпукло; не проверял).
Можно решать за O(n), сделав вместо тернарников три указателя. Такая задача была в Петрозаводске года 4 назад.
Так ?
Именно.
Оно же не работает, правда?
Не работает