This page is still under construction.

Parts of this page are still being built. What you see may change.

Star Pictures

Time limit3sMemory limit1024 MB

Summary
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 NN 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 (x,y)(x, y) to (x+u,y+v)(x + u, y + v) during the hour, for some integers uu and vv that are the same for all stars, but you do not know what uu and vv 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 NN (1≤N≤10001 \leq N \leq 1000), the number of points per picture.

The following NN lines contain two integers x_ix\_i and y_iy\_i (−106≤x_i,y_i≤106-10^6 \leq x\_i, y\_i \leq 10^6), the x- and y-coordinate of point number ii in the first picture.

After that follow another NN lines with two integers X_iX\_i and Y_iY\_i (−106≤X_i,Y_i≤106-10^6 \leq X\_i, Y\_i \leq 10^6), the x- and y-coordinate of point number ii 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.

Examples3

  1. Example 1

    Input
    2
    5 0
    3 0
    2 0
    6 0
    
    Expected output
    1
    
  2. Example 2

    Input
    4
    -3 0
    1 1
    -1 2
    2 3
    2 1
    -1 1
    1 3
    -2 0
    
    Expected output
    2
    
  3. Example 3

    Input
    5
    0 0
    1 5
    3 7
    2 9
    10 6
    3 -7
    6 0
    4 -2
    -1 2
    -9 5
    
    Expected output
    2