Problem S. 153. (May 2021)
S. 153. Subscribers can reach the text of the problem after signing in. The text will be public from May 28, 2021.]
(10 pont)
Deadline expired on June 15, 2021.
Sorry, the solution is available only in Hungarian. Google translation
Az egyetlen 10 pontos megoldáshoz gratulálunk Horcsin Bálintnak:
A feladat hatékony megoldása implementációtól és egyéb részletektől függetlenül ugyan az volt: Keressük meg azokat a csúcsokat, melyek az új pont felvételével a konvex burkon belülre kerülnek. Ezt meg lehet csinálni Horcsin Bálint megoldása szerint a sokszög eltolásával és egy ügyes rendezési függvénnyel, vagy egyszerű bináris kereséssel is. Ilyenkor két olyan érinitőt keresünk a sokszöghöz, melyek áthaladnak az újonnan felvett ponton.
A komplexitás minden esetben \(\displaystyle O(N*log(N))\)
Statistics:
4 students sent a solution. 10 points: Horcsin Bálint. 3 points: 2 students. 0 point: 1 student.
Problems in Information Technology of KöMaL, May 2021