#P2367. Ural 1478 spy satellites

    ID: 1410 传统题 1000ms 128MiB 尝试: 21 已通过: 7 难度: 7 上传者: 标签>CF2200提高Kruskal 重构树普通并查集树上背包平方距离比较同时事件分阶段处理

Ural 1478 spy satellites

题目描述

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

现在我们想知道把城镇划分成多少个区是可行的。

输入格式

第 11 行为一个整数 nn,表示城镇的个数。

接下来 nn 行,每行两个数 x,yx,y,描述每个城镇的坐标。

输出格式

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

样例输入

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

样例输出

1 4

数据规模与约定

对于 30%30\% 的数据 1≤n≤101\le n\le 10。

对于 100%100\% 的数据 1≤n≤3001\le n\le 300,−104≤x,y≤104-10^4\le x,y\le 10^4。