oj mrJudge
Toggle navigation
  • Login
    • Forget Password
      Login
User Image

Hello, Stranger

Guest
  • Analysis Mode
  • Problems
    • All Problems
    • Latest Problems
  • Join Us Now
  • Registration
  • Contact Us
  • Infomation
  • About
    • Terms of Use
    • Technical Specifications
    • Credits

dotjoin Batch , stdin/stdout

Registered Users Only

Please login to utilize this feature.

Do note that this website only supports submissions in C++.

dotjoin.html

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.

Input

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

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

Limits

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

Input:

4
0 0
0 2
2 0
1 1
Output:
1
Explanation:
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.

Tags

Minimum Spanning Tree, Graph Theory

Subtasks and Limits

Subtask Score #TC Time Memory Scoring
110102s64MBMinimum
221102s64MBMinimum
322102s64MBMinimum
447102s64MBMinimum
5012s64MBMinimum

Judge Compile Command

g++-8 ans.cpp -o dotjoin -Wall -Wshadow -static -O2 -lm -m64 -s -w -std=gnu++17 -fmax-errors=512

Accepted Submissions

subIDUserTimeMax Time

Past Submissions

subIDUserTimeScore
mrJudge 09.05.20
Copyright © 2020 mrJudge. All rights reserved.