루미 알고리즘

#1488플래티넘Snurriga stolpar

PO 2020 결선코딩출제 David Wärn, Hugo Eberhard스웨덴어 원문이 문제가 어렵다면 — 배우는 순서 보기

스웨덴어 원문입니다. 원문의 수식·표를 글자로 옮겨 모양이 다를 수 있습니다. 정확한 내용은 원문 페이지에서 확인하세요. 원문 페이지 열기 (새 창)

Problem

OBS!!! Denna uppgift handlar inte om samma sorts stolpar som gruppindelning

Din flygande matta har börjat strula! Så länge den är tom är allt frid och fröjd, och den kan flyga var som helst i planet utan problem. Men så fort den lastats med något, så som magiska oljelampor, kan den inte längre svänga själv, utan måste svänga vid så kallade snurriga stolpar. Eftersom de snurriga stolparna bara kan rotera motsols 90 grader åt gången så kan mattan också bara svänga exakt 90 grader motsols i varje sväng. Dessutom blir den så snabbt överhettad att den lämnar ett brinnande spår efter sig så snart den är lastad med något. Därför kan den inte heller svänga flera gånger vid samma stolpe, det skulle ta så lång tid att den brann upp. Den kan inte heller korsa sin egen väg eller besöka en stolpe som den redan varit vid.

Och självklart är det just nu, när mattan är i sämre skick än någonsin, som du behöver den som mest. Rafaj har nämligen spridit ut alla sultanens magiska oljelampor på stans snurriga stolpar. Du måste nu samla in så många oljelampor som möjligt innan någon råkar släppa ut andarna och katastrofen blir ett faktum.

I planet finns n snurriga stolpar med heltalskoordinater och på varje stolpe finns nu en magisk oljelampa. Du vill besöka så många stolpar som möjligt med den flygande mattan, genom att vandra på följande sätt:

  • Du får börja vid godtycklig stolpe, eftersom mattan kan flyga obehindrat då den är tom
  • Du får bara röra dig upp/ner/vänster/höger
  • Du får bara svänga vid stolpar, och bara 90 grader motsols (du kan alltså inte svänga medsols eller byta håll, du kan dock fortsätta rakt fram)
  • Din väg får inte korsa sig själv, eller besöka en stolpe flera gånger, då brinner mattan upp

Hur många stolpar kan du besöka?

Indata

Den första raden innehåller ett heltal n (1 ≤ n ≤ 1000). Därefter följer n rader. Den i:te raden innehåller två positiva heltal x_i, y_i (1 ≤ x_i, y_i ≤ 10^9), den i:te stolpens koordinater. Det kommer aldrig att stå två stolpar på samma position.

Utdata

Skriv ut en rad med ett heltal, det största antal stolpar du kan besöka.

Poängsättning

Din lösning kommer att testas på en mängd testfallsgrupper. För att få poäng för en grupp så måste du klara alla testfall i gruppen.

GruppPoängvärdeGränser
119n ≤ 25, x_i, y_i ≤ 5
216n ≤ 80, x_i, y_i ≤ 80
320n ≤ 80
445Inga ytterligare begränsningar

예제

예제 1

입력
6
1 1
1 4
2 2
3 2
3 4
5 4
출력
5

예제 2

입력
3
1 1
2 2
3 3
출력
1

예제 3

입력
10
1 1
1 100
23 62
41 77
41 100
23 37
47 62
89 37
41 83
89 100
출력
8

예제 4

입력
3
1 1
1 2
1 3
출력
3

출처 표기

출처: Programmeringsolympiaden 2020년 결선 · 원문 페이지 · 이용 조건 CC BY-SA · LaTeX 원문을 화면용 글로 옮겼습니다(수식·표의 모양이 다를 수 있습니다). 내용은 고치지 않았습니다.

크리에이티브 커먼즈 저작자표시-동일조건변경허락.

문제 출처: 한국정보올림피아드(KOI) (CC BY-NC-SA 4.0) · International Olympiad in Informatics (IOI) (CC BY) · Centre for Education in Mathematics and Computing (CEMC), University of Waterloo (CC BY-NC 4.0) · Programmeringsolympiaden (CC BY-SA) · CSES Problem Set (Antti Laaksonen) (CC BY-NC-SA 4.0). 루미 알고리즘은 위 단체들과 관계없는 별도의 서비스이며, 자료는 원문 그대로 싣습니다. 문제마다 출처와 이용 조건을 따로 표기합니다.