2014 Canadian Computing Competition, Stage 1

Problem S5: Lazy Fox

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

The first line contains the integer N (1 ≤ N ≤ 2000). The next N lines each contain Xi, followed by a space, followed by Yi, for i = 1..N (−10 000 ≤ Xi, Yi ≤ 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 ≤ 50;
  • at least 40% of the marks will be for test cases where N ≤ 200;
  • the remaining marks will be for test cases where N ≤ 2000.

Output

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

Sample Output

6

Explanation

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

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

All Submissions
Best Solutions


Point Value: 20 (partial)
Time Limit: 2.00s
Memory Limit: 64M
Added: Feb 27, 2014
Author: SourSpinach

Languages Allowed:
C++03, PAS, C, HASK, ASM, RUBY, PYTH2, JAVA, PHP, SCM, CAML, PERL, C#, C++11, PYTH3

Comments (Search)

Can anybody who got perfect or somewhat good score explain how to do this?

Here's a hint: sort.

I actually have a working code in java but I can never make my program work for under 5 seconds which is the requirement. I just calculate all edges between nodes, sort them and save them in a list then just DFS with saved subtrees. I can get it down to about 7-8 seconds but I cant for the life of me make it work under 5s which is the requirement for the question