Hide

Problem B
Stjärnbilder

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 \leq N \leq 1000$), antalet punkter per bild.

De följande $N$ raderna innehåller två heltal $x_ i$ och $y_ i$ ($-10^6 \leq x_ i, y_ i \leq 10^6$), x- och y-koordinat 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 \leq X_ i, Y_ i \leq 10^6$), x- och y-koordinat 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.

Grupp

Poängvärde

Gränser

$1$

$24$

Det finns max $1$ rymdskepp.

$2$

$39$

$N \leq 200$

$3$

$37$

Inga ytterligare begränsningar.

Sample Input 1 Sample Output 1
2
5 0
3 0
2 0
6 0
1
Sample Input 2 Sample Output 2
4
-3 0
1 1
-1 2
2 3
2 1
-1 1
1 3
-2 0
2
Sample Input 3 Sample Output 3
5
0 0
1 5
3 7
2 9
10 6
3 -7
6 0
4 -2
-1 2
-9 5
2

Please log in to submit a solution to this problem

Log in