CCC '14 S5 - Lazy Fox

View as PDF
Submit solution
Points: 20 (partial)
Time limit: 1.0s
Memory limit: 256M
Author:
SourSpinach
Problem type
Canadian Computing Competition: 2014 Stage 1, Senior #5

You have a pet Fox who loves treats. You have N neighbours at distinct locations (described as points on the Cartesian plane) which hand out treats to your pet Fox, and each neighbour has an unlimited number of treats to give out. The origin (which is where the Fox starts) will not be one of these N locations.

What does the Fox say, in order to get these treats? That is a good question, but not our concern. The Fox moves from location to location to gather exactly one treat from each location on each visit. He can revisit any previous location, but cannot visit the same location on two consecutive visits.

Your Fox is very lazy. The distance your Fox is willing to travel after each treat will strictly decrease. Specifically, the distance from the origin to his first treat location must be larger than the distance from his first treat location to his second treat location, which in turn is larger than the distance between his second treat location and his third treat location, and so on.

What is the largest number of treats your Fox gathers?

Input Specification

The first line contains the integer N (1 \le N \le 2000). The next N lines each contain X_i, followed by a space, followed by Y_i, for i = 1 \dots N (-10\,000 \le X_i, Y_i \le 10\,000) representing the coordinates of the i^{th} location. The following additional constraints will apply:

  • At least 20% of the marks will be for test cases where N \le 50;
  • at least 40% of the marks will be for test cases where N \le 200;
  • the remaining marks will be for test cases where N \le 2000.

Output Specification

The output is one integer, the largest number of treats your Fox can gather.

Sample Input

5
5 8
4 10
3 1
3 2
3 3

Output for Sample Input

6

Explanation of Output for Sample Input

The Fox performs the visits in the following order (with the indicated distances):

  • (0, 0) to (4, 10) with distance \sqrt{116};
  • (4, 10) to (3, 1) with distance \sqrt{82};
  • (3, 1) to (5, 8) with distance \sqrt{53};
  • (5, 8) to (3, 3) with distance \sqrt{29};
  • (3, 3) to (3, 1) with distance 2;
  • (3, 1) to (3, 2) with distance 1.

Comments


  • 5
    Subway_Man  commented on March 31, 2020, 10:53 p.m.

    Appears to be impossible for both Python 3 and PyPy 3 with the constraints given.


    • 2
      noYou  commented on Aug. 13, 2020, 10:07 p.m.

      This seems to be true, there are no AC submissions. A language specific Time limit could be implemented.


  • 21
    mattpk  commented on Sept. 29, 2017, 3:45 a.m.

    Memory/Time limit seems overly strict for Java.


  • 6
    Xue_Alex  commented on June 26, 2017, 5:59 p.m. ← edited

    When the question states "origin", does that mean the origin as described in a Cartesian plane (so at (0, 0)), or does it just mean the Fox's starting position (as in the Fox may start at any coordinate between -10\,000 and 10\,000).


    • 14
      wleung_bvg  commented on June 26, 2017, 7:00 p.m. ← edited

      The origin is (0, 0), which is also where the fox starts.


  • 8
    JeffreyZ  commented on Feb. 8, 2016, 5:40 p.m. ← edit 3

    Can the fox travel back to the origin after visiting a neighbour?

    EDIT: Probably not.


    • 8
      aurpine  commented on Feb. 9, 2016, 1:48 a.m.

      No because it's not one of the "locations"


      • -9
        gj504772  commented on Feb. 16, 2023, 1:21 a.m. ← edit 2

        This comment is hidden due to too much negative feedback. Show it anyway.