2 shunfurh shunfurh 于 2017.01.04 23:34 提问

星系碰撞

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
61 39 111 75 713 54 4
Sample Output
4

1个回答

caozhy
caozhy   Ds   Rxr 2017.01.12 00:44
已采纳
Csdn user default icon
上传中...
上传图片
插入图片
准确详细的回答,更有利于被提问者采纳,从而获得C币。复制、灌水、广告等回答会被删除,是时候展现真正的技术了!