Sniping

Time limit1.5sMemory limit256 MB

Summary
Place up to 20 enemies onto rays from two sniping spots with structured piercing sets, minimizing bullets then spot moves.
Level

Medium7 of 10

Topics
Geometry, Brute force, Combinatorics, Bit manipulation
Solved
No attempts yet

Problem

Sinon is a famous sniper in GGO (Gun Gale Online). She is practicing hard again today for BoG (Bullets of GSHS).

Today's practice is to get used to her new weapon, the 'Hecate'.

The Hecate is a gun with much greater penetration than the existing Hecate, and it can hit multiple people at once along the ray that extends in the direction the gun is fired.

Sinon has two favorite sniping spots. She snipes only from these two spots, and she is currently at the first sniping spot.

Through a satellite scan she knows the coordinates of the enemies, and she wants to defeat all the enemies with as few bullets as possible.

Also, if all enemies can be hit with the same number of bullets, she wants the number of times she moves spots to be as small as possible.

Help Sinon and find the minimum number of bullets needed to hit all enemies and the minimum number of spot moves.

The two sniping spots are guaranteed to be at different positions, and a sniping spot never coincides with an enemy's position. However, multiple enemies can be at the same position.

Input

The first line gives the number of enemies NN (1≤N≤201 \le N \le 20).

Then, over NN lines, the coordinates xenemyi,yenemyix_{enemy_i}, y_{enemy_i} where each enemy is located on the xyxy plane are given. (−109≤xenemyi,yenemyi≤109-10^9 \le x_{enemy_i}, y_{enemy_i} \le 10^9)

After that, over two lines, the coordinates xsinoni,ysinonix_{sinon_i}, y_{sinon_i} where Sinon's two favorite sniping spots are located are given. (−109≤xsinoni,ysinoni≤109-10^9 \le x_{sinon_i} , y_{sinon_i} \le 10^9)

However, among the coordinates of Sinon's two favorite sniping spots, the coordinate given first is the coordinate of the sniping spot where Sinon is currently located.

Output

Print the minimum number of bullets needed and, for that, the minimum number of spot moves, separated by a space on one line.

Examples3

  1. Example 1

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

    Input
    4
    1 2
    2 4
    2 14
    1 9
    0 0
    0 4
    
    Expected output
    2 1
    
  3. Example 3

    Input
    2
    1 0
    -1 0
    0 0
    3 0
    
    Expected output
    1 1