Ural 1478 spy satellites

时间限制:3s      空间限制:128MB

题目描述

城镇划分
n个城镇,每个城镇描述为平面上一个点(x,y),我们想把其中一些城镇划分在一起,以便于管理。划分在一起的城镇称之为一个区,必须保证一个区中城镇之间的距离都严格小于区中城镇到区外城镇的距离。
现在我们想知道把城镇划分成多少个区是可行的。
 


输入格式

第1行为一个整数n,表示城镇的个数。
接下来n行,每行两个数x,y,描述每个城镇的坐标。
 


输出格式

一行若干个整数,表示所有可行的城镇划分个数,数之间用一个空格隔开并且严格递增。
 


样例输入

4
-1 -1
1 1
1 -1
-1 1
 

样例输出

1 4
 

提示

数据范围:
-10000<=x,y<=10000
对于30%的数据 1<=n<=10
对于100%的数据 1<=n<=300


题目来源

没有写明来源

Menuappsclose