루미 알고리즘

#1489골드Stjärnbilder

PO 2020 결선코딩출제 Erik Amirell Eklöf스웨덴어 원문이 문제가 어렵다면 — 배우는 순서 보기

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

Problem

I en galax långt, långt borta har Pletiapan, som ett steg i sin ondskefulla plan att ta över hela galaxen, infört tullavgifter för alla rymdskepp som passerar ovanför Trädandssjön. Nu har han fått nys om att ett gäng smugglare med den ökända Nola Sho i spetsen hittat ett sätt att ta sig runt hans toppmoderna scannersystem. Men frukta inte! Pletiapan har givetvis en plan för hur han ska sätta dit de lömska smugglarna, en plan som bara kan gå i lås med din hjälp. I källaren har han nämligen en gammal analog kamera, och om ni använder den för att ta två bilder av himlen kan ni sen jämföra dem för att avgöra hur många rymdskepp som minst måste passera över Trädandssjön. Om det är fler än vad som betalat tull så måste det vara något skumt i görningen, och eftersom ingen kan minnas senaste gången något skumt hände utan Nola Shos inblandning så skulle det praktiskt taget vara tillräckligt för att sätta dit honom en gång för alla.

Pletiapan kommer alltså ge dig två bilder. I varje bild finns N stycken ljusa punkter, och varje punkt har en x- och en y-koordinat. En punkt är antingen en stjärna eller ett rymdskepp, men du vet inte vilket. Du vet dock att varje stjärna förflyttat sig från (x, y) till (x + u, y + v) under timmen, för några heltal u och v som är samma för alla stjärnor, men du vet inte vad u och v är. Ett rymdskepp kan däremot ha flyttat sig från vilken punkt som helst till vilken annan punkt som helst. Alla stjärnor/rymdskepp i den ena bilden finns också med i den andra.

Hur många rymdskepp kan man vara säker på att det finns i bilderna?

Indata

Den första raden innehåller ett heltal N (1 ≤ N ≤ 1000), antalet punkter per bild.

De följande N raderna innehåller två heltal x_i och y_i (-10^6 ≤ x_i, y_i ≤ 10^6), x- och y-koordinaterna för punkt nummer i i den första bilden.

Efter det följer ytterligare N rader med två heltal X_i och Y_i (-10^6 ≤ X_i, Y_i ≤ 10^6), x- och y-koordinaterna för punkt nummer i i den andra bilden.

Alla punkter i samma bild är unika.

Utdata

Skriv ut en rad med ett heltal, det minsta antalet rymdskepp som måste finnas i bilderna.

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
124Det finns som mest 1 rymdskepp.
239N ≤ 200
337Inga ytterligare begränsningar.

예제

예제 1

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

예제 2

입력
4
-3 0
1 1
-1 2
2 3
2 1
-1 1
1 3
-2 0
출력
2

예제 3

입력
5
0 0
1 5
3 7
2 9
10 6
3 -7
6 0
4 -2
-1 2
-9 5
출력
2

출처 표기

출처: 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). 루미 알고리즘은 위 단체들과 관계없는 별도의 서비스이며, 자료는 원문 그대로 싣습니다. 문제마다 출처와 이용 조건을 따로 표기합니다.