Fraktal XII

Szkoda, że informacja o godzinie zakończenia konkursu nie była zamieszczona na stronie SPOJ konkursu - przez to przepadło mi rozwiązanie do jednego zadania.
Proszę o omówienie zadania “parkrun Fraktalocja”.

Moglibyśmy zrobić tak jak sugerujesz, ale wtedy pewnie znajdą się osoby, które będą chciały żeby wszystkie zadania były dostępne od początku bo drugiego dnia nie mają czasu na ich rozwiązywanie. Ciężko jest dogodzić wszystkim FRAKTAL trwa dwa dni dlatego, że w założeniu to jest konkurs dla osób mniej doświadczonych, które potrzebują więcej czasu na zmierzenie się z tymi zadaniami. W praktyce wczorajszy zwycięzca to tegoroczny finalista Potyczek Algorytmicznych

Może podana, ale nie w zapowiedzi dwunastej edycji

image.png923x395 49.9 KB

No tak, mniej doświadczone osoby mogą sobie wybrać łatwiejsze zadanka z tych 20 i mieć zabawę dłuższą zabawę niż w moim wariancie gdzie zatrzymaliby się wcześniej na jakimś trudniejszym zadaniu, może jestem zbyt przyzwyczajony do formy na CodeForces I tak super że coś organizujecie

Omówienie tego zadania przedstawi Marcin na stronie fejsbukowej i na stronie algorytm.edu.pl26, ale tak w skrócie: należało wyznaczyć otoczkę wypukłą dla wczytanych punktów i obliczyć pole wyznaczonego wielokąta. Następnie usunąć z wczytanych na wejściu punktów punkty z otoczki i ponownie wyznaczyć otoczkę dla pozostałych punktów, po czym obliczyć pole wyznaczonego wielokąta. Od pola pierwszego wielokąta odejmujemy pole drugiego i dzielimy przez 4.

Ja jeszcze dodam do tego, co napisał Mariusz, że tak naprawdę główną trudnością w tym zadaniu jest szybkie wyeliminowanie punktów należących do boków zewnętrznej otoczki wypukłej. Można to zrobić przerabiając algorytm Grahama w taki sposób żeby do otoczki wypukłej były dodawane nie tylko punkty będące skrętem w lewo względem ostatniego już wyznaczonego odcinka otoczki, ale także te, które są współliniowe. To na co należy zwrócić szczególną uwagę to odpowiednie posortowanie punktów w przypadku gdy porównujemy dwa punkty współliniowe. W takim wypadku jeżeli porównywane punkty leżą po prawej stronie pierwszego punktu (P0) wyznaczanej otoczki to pierwszy z nich powinien być ten położony bliżej P0, w przeciwnym wypadku pierwszy powinien być ten punkt bardziej oddalony od P0.

Pewnie masz rację. Ja wiedziałem, że gdzieś musi być informacja o terminie zakończenia, więc jej szukałem w środku

Nie zrobiłeś tego. Funkcja ccw zwraca prawdę czyli, że punkt nie jest częścią otoczki jeżeli tworzy on skręt w prawo albo jest współliniowy (det >= 0). Czyli tak naprawdę wykluczasz punkty współliniowe, a dopiero potem je dodajesz w dalszej części algorytmu. To jest zdecydowanie nieoptymalne rozwiązanie. Zamiast tego powinieneś wykluczać tylko te punkty, które są skrętem w prawo czyli det > 0 w funkcji ccw. Wtedy to późniejsze dodawanie punktów współliniowych nie jest potrzebne. Przy takim podejściu i odpowiednim sortowaniu, o którym pisałem wyżej dostaniesz AC.

PS. Skoro x i y są int64_t to po co det w ccw jest typu double? Lepiej żeby też był int64_t, po pierwsze szybciej po drugie nie tracisz precyzji.

Dla mnie taka formuła jest zdecydowanie lepsza. Miałem pracę i w sobotę i w niedzielę. Dzięki tej formule mogłem rozwiązać chociaż kilka zadań. No, ale pewnie są też zwolennicy Twojego podejścia. Nie da się wszystkich zadowolić

Dziękuję za szczegółowe wyjaśnienie. Ten double został po tym, jak zmiana int na int64_t sprawiła zmianę statusu z WA na TLE i umknęło mi to później.