Problem Description

Rar the Cat has a list of N dots on a piece of paper. He asked K other cats to draw lines on the piece of paper such that each cat will connect all the dots once. The cats are known to draw the shortest total distance of lines to achieve their objective (connect all the dots). However, a cat cannot draw another line between a point A and point B directly if a line has been already drawn between point A and point B by a previous cat (or itself). (Each cat must connect all the dots without drawing over another cat's lines in successive order and each cat will always minimize the total distance it draws during its turn.)

Your task is to find the largest number of cats (maximum K) that Rar the Cat can ask to draw in successive order.


The first line of input consists of a single integer, N.

The following N lines consists of 2 integers each: X followed by Y. They are the X and Y co-ordinates of the point. There will be a total of N points described by N lines. X and Y will both have a difference of not more than 1million from 0.


Output the maximum K, the maximum number of other cats Rar the Cat can ask.


Subtask 1 (10%): 0 < N ≤ 10

Subtask 2 (21%): 0 < N ≤ 100

Subtask 3 (22%): 0 < N ≤ 500

Subtask 4 (47%): 0 < N ≤ 1000

Subtask 5 (0%): As per Sample Testcases.

Sample Testcase 1


0 0
0 2
2 0
1 1
Rar the Cat can ask one cat to draw, and the first cat will draw lines between (0, 0) to (1, 1), (0, 2) to (1, 1), (2, 0) to (1, 1). This will However, Rar the Cat cannot ask another cat to draw as no line can be drawn to the point (1, 1) already.

Submitting .cpp to 'dotjoin'

You're not logged in! Click here to login

Compile Errors

Time Limit: 2 Seconds
Memory Limit: 256MB
No. of ACs: 40
Your best score: 0
Source: Dunjudge Archive

Subtask Score
1 10
2 21
3 22
4 47