AT_s8pc_2_g.道とN個のAtCoder社
通过率:0%
AC君温馨提醒
该题目为【atcoder】题库的题目,您提交的代码将被提交至atcoder进行远程评测,并由ACGO抓取测评结果后进行展示。由于远程测评的测评机由其他平台提供,我们无法保证该服务的稳定性,若提交后无反应,请等待一段时间后再进行重试。
题目描述
Atcoder 公司有 N 个工厂。
217X 年,有一件事困扰着这个公司。那就是工厂和工厂之间没有道路。
运输公司的社长说:“这可是个大问题!可不能一直这样下去!”
于是,必须现在、立刻、马上制定修路计划。
由于这家公司做的事运输相关的工作,他们必须把产品从地方尽快地运到城市,从城市尽快地运到地方。因此,如果公司修路的话,就可以应付很多的订单。
但是,必须要在以下条件下修路。
- 为了提升运输卡车的速度,道路必须呈直线。
- 因为立交桥会大幅度地增大费用,所以道路与道路之间不能在除工厂以外的地方交叉。
- 在加快所有专用道路速度的基础上,得尽快到达目的地,于是要尽量加快道路速度。
- 道路连接工厂和工厂。
只不过,公司找不到最优的解决方案。
于是,作为最优秀的程序员的你,被公司委托来寻找最优的解决方案。请求出可建的最多道路条数。
但是,你必须严格遵守文中的条件。
注意:问题中的 217X 年是超时空世界的时间。在这里的时间可以视为现在。
输入格式
输入按照以下格式。
$ N $
$ x_1 $ $ y_1 $
$ : $ $ : $
$ x_N $ $ y_N $
- 第 1 行,工厂数量 N。
- 第 2 至(n+1)行,第 i 个工厂的坐标 (xi,yi)。
输出格式
输出按照以下格式。
- 输出 1 行,可建的最多道路条数。
输入输出样例
输入#1
4 0 0 1 1 0 1 1 0
输出#1
5
输入#2
4 0 0 1 2 2 0 1 1
输出#2
6
说明/提示
样例解释1
结点1和2、1和3、2和3、1和4、2和4之间可以建5条路。
样例解释2
这种情况,所有结点之间都可以修建路。
输入解题思路,AI测评打分。不知道怎么写?