별자리
시간 제한3초메모리 제한1024 MB
각각 N개의 점으로 이루어진 두 사진이 주어지고, 별은 모두 같은 미지의 벡터 (u,v)만큼 이동하지만 우주선은 어디로든 움직일 수 있을 때, 자료와 모순되지 않는 우주선의 최소 개수를 구한다.
문제
머나먼 은하에서, 은하 전체를 지배하려는 사악한 계획의 일환으로 Pletiapan은 Trädandssjön 상공을 지나는 모든 우주선에 통행세를 부과했다. 그런데 악명 높은 Nola Sho가 이끄는 밀수꾼 무리가 그의 최첨단 스캐너 시스템을 우회할 방법을 찾아냈다는 정보를 입수했다. 하지만 걱정할 필요는 없다! Pletiapan은 교활한 밀수꾼들을 잡을 계획을 세워 두었고, 그 계획은 당신의 도움 없이는 성공할 수 없다. 그의 지하실에는 낡은 아날로그 카메라가 있는데, 이것으로 하늘을 두 번 찍은 뒤 두 사진을 비교하면 Trädandssjön 상공을 최소 몇 척의 우주선이 지나야 하는지 알 수 있다. 통행세를 낸 수보다 많다면 뭔가 수상한 일이 벌어지고 있는 것이고, Nola Sho가 연루되지 않은 수상한 일은 아무도 기억하지 못하므로 그것만으로도 그를 완전히 잡을 수 있다.
Pletiapan은 당신에게 두 장의 사진을 줄 것이다. 각 사진에는 개의 밝은 점이 있고, 각 점은 x좌표와 y좌표를 가진다. 점은 별이거나 우주선이지만 어느 쪽인지는 알 수 없다. 다만 각 별은 한 시간 동안 에서 로 이동했고, 정수 와 는 모든 별에 대해 같지만 그 값은 알 수 없다. 반면 우주선은 어떤 점에서든 다른 어떤 점으로든 이동할 수 있다. 한 사진에 있는 모든 별과 우주선은 다른 사진에도 있다.
두 사진에 반드시 존재한다고 확신할 수 있는 우주선은 몇 척인가?
입력
첫째 줄에는 정수 ()이 주어지며, 이는 사진당 점의 수이다.
다음 개 줄에는 두 정수 와 ()가 주어지며, 첫 번째 사진의 번째 점의 x좌표와 y좌표이다.
그다음 개 줄에는 두 정수 와 ()가 주어지며, 두 번째 사진의 번째 점의 x좌표와 y좌표이다.
같은 사진에 있는 모든 점은 서로 다르다.
출력
두 사진에 반드시 존재해야 하는 우주선의 최소 수를 한 줄에 정수로 출력한다.