AT_s8pc_2_g 道とN個のAtCoder社
题目描述
Atcoder 公司有 $N$ 个工厂。
$217X$ 年,有一件事困扰着这个公司。那就是工厂和工厂之间没有道路。
运输公司的社长说:“这可是个大问题!可不能一直这样下去!”
于是,必须现在、立刻、马上制定修路计划。
由于这家公司做的事运输相关的工作,他们必须把产品从地方尽快地运到城市,从城市尽快地运到地方。因此,如果公司修路的话,就可以应付很多的订单。
但是,必须要在以下条件下修路。
- 为了提升运输卡车的速度,道路必须呈直线。
- 因为立交桥会大幅度地增大费用,所以道路与道路之间不能在除工厂以外的地方交叉。
- 在加快所有专用道路速度的基础上,得尽快到达目的地,于是要尽量加快道路速度。
- 道路连接工厂和工厂。
只不过,公司找不到最优的解决方案。
于是,作为最优秀的程序员的你,被公司委托来寻找最优的解决方案。请求出可建的最多道路条数。
但是,你必须严格遵守文中的条件。
注意:问题中的 $217X$ 年是超时空世界的时间。在这里的时间可以视为现在。
输入格式
输入按照以下格式。
```
$ N $
$ x_1 $ $ y_1 $
$ : $ $ : $
$ x_N $ $ y_N $
```
- 第 $1$ 行,工厂数量 $N$。
- 第 $2$ 至$(n+1)$行,第 $i$ 个工厂的坐标 $(xi,yi)$。
输出格式
输出按照以下格式。
- 输出 $1$ 行,可建的最多道路条数。
说明/提示
**样例解释1**
结点1和2、1和3、2和3、1和4、2和4之间可以建5条路。
**样例解释2**
这种情况,所有结点之间都可以修建路。