Mock CCC '19 Contest 2 S5 - Tudor Takes Pictures of Goats

View as PDF
Submit solution
Points: 15
Time limit: 0.6s
Memory limit: 1G
Problem type

Tudor has decided to upload pictures of his goats to Instagram!

Tudor's goats are currently located at various lattice points in the xy-plane. To take pictures of his goats, Tudor will use a drone with a camera mounted on it. Tudor will send the drone to some point (x, y, z) with z > 0 and then take pictures of the goats from that location.

The camera that Tudor is using is a bit finicky - it can be set to focus on objects that are exactly d units away, but when that happens, it can only take pictures of objects that are exactly d units away. Since the location of the drone is fixed, if the camera needs to take a picture of an object that is a different distance away, it must be set to focus at the new distance.

The camera is smart enough to automatically take pictures of all objects of interest that are at its current focus distance. However, Tudor will need to manually instruct the camera on which distances to focus at. The camera initially has its focus distance set to zero.

Compute the minimum number of times Tudor will need to change the focus distance of the camera.

Constraints

1 \le N \le 40

-300 \le x_i, y_i \le 300

All goats are at distinct points.

There is no partial credit available for this problem.

Input Specification

The first line of input will contain a single positive integer, N.

Each of the next N lines will contain two space-separated integers, x_i and y_i, indicating a goat is at (x_i, y_i).

Output Specification

Output, on a single line, the minimum number of times Tudor needs to focus the camera.

Sample Input

8
3 4
0 5
0 -5
5 0
-5 0
4 -3
3 -4
-4 3

Sample Output

1

Comments


  • 1
    Roronoa_Zoro1540  commented on Feb. 12, 2019, 3:32 a.m.

    how does adding a third dimension make a difference to the problem? Could someone explain to me why it the answer wouldn't be the same if the drone was also only on the x-y plane, with no height?


    • 3
      aeternalis1  commented on Feb. 12, 2019, 3:41 a.m.

      The focus distance is initially set to zero, which means that if it's hovering above the ground it cannot initially focus on a goat directly beneath itself.