№ | Пользователь | Рейтинг |
---|---|---|
1 | tourist | 4009 |
2 | jiangly | 3823 |
3 | Benq | 3738 |
4 | Radewoosh | 3633 |
5 | jqdai0815 | 3620 |
6 | orzdevinwang | 3529 |
7 | ecnerwala | 3446 |
8 | Um_nik | 3396 |
9 | ksun48 | 3390 |
10 | gamegame | 3386 |
Страны | Города | Организации | Всё → |
№ | Пользователь | Вклад |
---|---|---|
1 | cry | 167 |
2 | Um_nik | 163 |
3 | maomao90 | 162 |
3 | atcoder_official | 162 |
5 | adamant | 159 |
6 | -is-this-fft- | 158 |
7 | awoo | 157 |
8 | TheScrasse | 154 |
9 | Dominater069 | 153 |
9 | nor | 153 |
Название |
---|
2 вариант работает для любого многоугольника.
Я использовал бинпоиск в своем решении. Мне хочется понять, где я ошибся. А 1-ый вариант у меня получился)
вариант 1 работает и для невыпуклых многоугольников, только нужно считать знаковую площадь (векторное произведение в помощь). Порядок обхода либо по часовой, либо против часовой — ну проверим оба варианта сравнив абсолютные величины.
Не правда, знаковая площадь не поможет. Нужно считать угол.
Да, похоже вру. Знаковая площадь может использоваться для вычисления площади невыпуклого многоугольника, а не того о чем спросил автор.
Разве гарантируется порядок обхода вершин в входных данных?
Для лучшего понимания можно попробовать тривиальный тест:
=======
4
0 0
0 2
2 2
2 0
1 1
=======
YES
=======
Насчет этого в условии задачи ничего не написано. Но мое решение прошло, которое работает при наличии порядка обхода. А ваш тест у меня не работает:(
Об этом Lord_F и говорит! — если что-то в условии не запрещено, значит [почти наверняка] это будет в одном из тестов:
-не сказано, что числа только целые — жди вещественные,
-не сказано, что скорость положительная — жди отрицательную,
-не сказано, что между городами ровно одна дорога — жди несколько дорог,
и т.д. Так что в каждой задаче ИЩИТЕ ПОДВОХ! :)
Спасибо за совет )