Star Pictures
Time limit3sMemory limit1024 MB
Given two pictures of N points each, stars all shift by one unknown vector (u,v) while spaceships may move anywhere; find the minimum number of spaceships consistent with the data.
- Level
Medium7 of 10
- Topics
- Hash map, Geometry, Brute force, Implementation
- Solved
- No attempts yet
Problem
In a galaxy far, far away, Pletiapan, as part of his evil plan to take over the entire galaxy, has imposed tolls on all spaceships passing above Trädandssjön. Now he has learned that a gang of smugglers led by the infamous Nola Sho has found a way around his state-of-the-art scanner system. But fear not! Pletiapan naturally has a plan to catch the cunning smugglers, a plan that can only succeed with your help. In his basement he has an old analog camera, and if you use it to take two pictures of the sky, you can then compare them to determine the minimum number of spaceships that must pass over Trädandssjön. If it is more than the number that paid the toll, something shady must be going on, and since no one can remember the last time something shady happened without Nola Sho's involvement, that would practically be enough to catch him once and for all.
Pletiapan will therefore give you two pictures. Each picture contains bright points, and each point has an x- and a y-coordinate. A point is either a star or a spaceship, but you do not know which. You do know that each star moved from to during the hour, for some integers and that are the same for all stars, but you do not know what and are. A spaceship, on the other hand, can have moved from any point to any other point. All stars and spaceships in one picture are also in the other.
How many spaceships can you be sure are in the pictures?
Input
The first line contains an integer (), the number of points per picture.
The following lines contain two integers and (), the x- and y-coordinate of point number in the first picture.
After that follow another lines with two integers and (), the x- and y-coordinate of point number in the second picture.
All points in the same picture are distinct.
Output
Print one line with an integer, the minimum number of spaceships that must be in the pictures.