提示: 欢迎访问OurACM平台。
Problem 2194 星系碰撞

Accept: 62    Submit: 215
Time Limit: 30000 mSec    Memory Limit : 327680 KB

Problem Description

据预测,大约在100亿年后,狮子座星系将与银河系发生碰撞,两个星系的碰撞将会合并两个星系,但是没有2个星球会相撞。现在某科学家得到两个星系合并后的结果,一些二维平面上的点,但是不知道那些星球属于银河系,已知如果两个星球属于同一个星系,那么他们之间的距离大于5光年,这边的距离指的是欧几里得距离,即(x1,y1)与(x2,y2)的距离为sqrt((x1-x2)*(x1-x2)+(y1-y2)*(y1-y2))。现在想请你帮忙把合并后的结果分成2个集合,一个属于银河系,一个属于狮子座星系,由于集合划分的方案可能有多种,现在想知道最多有多少个星球可能属于银河系。(可以所有星球都属于银河系)

例如:如下图有6个点,你可以有以下4中划分{{1, 2, 4, 5}, {3, 6}}; {{1, 2, 3, 4}, {5, 6}}; {{1, 4,5}, {2, 3, 6}}; {{1, 3, 4}, {2, 5, 6}} ,那么可以采用第一种划分{1,2,4,5} 都属于银河系,答案为4.

Input

包含多组数据 每组数据输入第一行 一个整数N 表示星球个数(1<=N<=50000),接下去N 行 每行2个整数 x和y 表示星球的坐标(1<=x,y<=500000),没有重合的点。

Output

输出一行一个整数表示最多有多少个星球属于银河系。如果没办法进行划分那么输出-1。

Sample Input

6 1 3 9 1 11 7 5 7 13 5 4 4

Sample Output

4

Source

福州大学第十二届程序设计竞赛

Submit  Back  Status  Discuss