Боря программирует

В субботу прошел третий раунд Meta HackerCup. Чтобы пройти в финал, нужно было попасть в топ25, что я успешно и сделал (ура!). Но пост не об этом.

Самая сложная задача в контесте, которую сдало всего 3 человека, по сути заключалась в написании стандартного алгоритма из курса вычислительной геометрии. Дано много многоугольников, и нам поступают запросы в виде точек. Про каждую точку надо быстро определять, в каком многоугольнике она лежит.

Стандартный алгоритм — сканирующая прямая и персистентное декартово дерево. Что в целом не так сложно, но писать довольно много (я, например, не успел). После конца контеста Паша Кунявский рассказал (https://www.tgoop.com/kunyavskiy_channel/120) о другом алгоритме, который, как мне кажется, сильно проще этого, но про который я раньше не слышал.

Так что решил не держать это знание в себе, а поделиться с человечеством: https://teletype.in/@bminaiev/online-point-location

🎉8🔥3

www.tgoop.com/bminaiev_blog/18

1.82K viewsedited  Oct 11, 2022 at 08:25

В субботу прошел третий раунд Meta HackerCup. Чтобы пройти в финал, нужно было попасть в топ25, что я успешно и сделал (ура!). Но пост не об этом.

Самая сложная задача в контесте, которую сдало всего 3 человека, по сути заключалась в написании стандартного алгоритма из курса вычислительной геометрии. Дано много многоугольников, и нам поступают запросы в виде точек. Про каждую точку надо быстро определять, в каком многоугольнике она лежит.

Стандартный алгоритм — сканирующая прямая и персистентное декартово дерево. Что в целом не так сложно, но писать довольно много (я, например, не успел). После конца контеста Паша Кунявский рассказал (https://www.tgoop.com/kunyavskiy_channel/120) о другом алгоритме, который, как мне кажется, сильно проще этого, но про который я раньше не слышал.

Так что решил не держать это знание в себе, а поделиться с человечеством: https://teletype.in/@bminaiev/online-point-location

BY Боря программирует