AT_s8pc_2_g.道とN個のAtCoder社

通过率:0%

AC君温馨提醒

该题目为【atcoder】题库的题目,您提交的代码将被提交至atcoder进行远程评测,并由ACGO抓取测评结果后进行展示。由于远程测评的测评机由其他平台提供,我们无法保证该服务的稳定性,若提交后无反应,请等待一段时间后再进行重试。

题目描述

Atcoder 公司有 NN 个工厂。

217X217X 年,有一件事困扰着这个公司。那就是工厂和工厂之间没有道路。

运输公司的社长说:“这可是个大问题!可不能一直这样下去!”

于是,必须现在、立刻、马上制定修路计划。

由于这家公司做的事运输相关的工作,他们必须把产品从地方尽快地运到城市,从城市尽快地运到地方。因此,如果公司修路的话,就可以应付很多的订单。

但是,必须要在以下条件下修路。

  • 为了提升运输卡车的速度,道路必须呈直线。
  • 因为立交桥会大幅度地增大费用,所以道路与道路之间不能在除工厂以外的地方交叉。
  • 在加快所有专用道路速度的基础上,得尽快到达目的地,于是要尽量加快道路速度。
  • 道路连接工厂和工厂。

只不过,公司找不到最优的解决方案。

于是,作为最优秀的程序员的你,被公司委托来寻找最优的解决方案。请求出可建的最多道路条数。

但是,你必须严格遵守文中的条件。

注意:问题中的 217X217X 年是超时空世界的时间。在这里的时间可以视为现在。

输入格式

输入按照以下格式。

$ N $ 
$ x_1 $   $ y_1 $ 
$ : $   $ : $ 
$ x_N $   $ y_N $ 
  • 第 11 行,工厂数量 NN。
  • 第 22 至(n+1)(n+1)行,第 ii 个工厂的坐标 (xi,yi)(xi,yi)。

输出格式

输出按照以下格式。

  • 输出 11 行,可建的最多道路条数。

输入输出样例

  • 输入#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测评打分。不知道怎么写?

首页