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** 这种情况,所有结点之间都可以修建路。