Solutia problemei Expand

O soluţie care merge bine pe poligoane regulate este să calculăm un punct G ca fiind media aritmetică a tuturor vârfurilor poligonului (adică abscisa lui G este media aritmetică dintre abscisele tuturor vârfurilor, la fel şi ordonata lui G este media aritmetică dintre ordonata tutoror vârfurilor), şi să mutăm fiecare punct diametral opus faţă de G. Această soluţie ar obţine aproximativ 44 de puncte.

O idee ar fi să luăm mai multe puncte potenţiale pentru fiecare vârf, apoi ne fixăm un vârf şi calculăm o dinamică de tipul dp[i][j] = aria maximă pe care o putem obţine dacă am fixat primele i vârfuri, iar vârful i l-am fixat în al j-lea punct potenţial pentru el. Cea mai bună soluţie implementată de comisie pe această idee obţine 76 de puncte.

O altă idee ar fi să incercăm să fixăm optim fiecare vârf în felul următor : fie 3 vârfuri consecutive A, B, C. Considerăm că A şi C sunt fixate. Ducem perpendiculara din B pe AC şi îl mutăm pe B în punctul B' de pe perpendiculara care se află la distanţa R faţă de B (cum sunt două puncte B', îl alegem pe cel mai depărtat faţă de dreapta AC). Pentru o soluţie cât mai bună, repetăm de mai multe ori strategia asta. O soluţie de genul ar trebui să obţină 100 de puncte. Fără a repeta de mai multe ori strategia se obţin ~92 de puncte.