P2443 [SDOI2005]高速公路

    • 0通过
    • 7提交
  • 题目提供者 zzq123
  • 评测方式 云端评测
  • 标签 各省省选 2005 山东
  • 难度 尚无评定
  • 时空限制 1000ms / 128MB

题解

  • 提示:收藏到任务计划后,可在首页查看。
  • 体验新版界面

    最新讨论 显示

    推荐的相关题目 显示

    题目描述

    京珠高速公路目前正在建设当中。粤北地区是世界著名的“丹霞地貌”,京珠在这里必须穿过一大片复杂的山区。工程的总设计师Bonny已经规划好了公路大致的走向,而工程师们则被派往各个多山的路段,以设计这些路段的具体规划。

    现在,你因为在信息学上取得的出色成就,被Bonny派往一个称为DreadfulMess的最复杂的路段,并仅仅给了你一张地图和一些数据。

    地图以笛卡尔坐标系描述,其中包括这一地区的所有山峰的数据(俯视图)及两个点A、B。每座山的轮廓被假想为四边形,工程师们把这些四边形的顶点称为“测量点” ,这些四边形不会发生重叠、包含,但有可能有共用的一段边或顶点。山以外的区域被认为是平地。

    你的任务是计算此路段山区的总面积,并设计一条公路,从A点起始,到B点终止。设计的原则是:公路是一条折线(即转弯点的个数是有限的);公路可以修在平地上、沿山脚或山谷(即两座山的结合部),也可以打隧道;隧道口不能是转弯点,除非它又是测量点;修建公路的费用最小。

    费用的计算:平地、沿山脚或山谷的单位修路费用为u0,各座山修隧道的单位费用为ui。

    输入输出格式

    输入格式:

    第一、二行分别为A、B点坐标,整数。

    第三行为u0,正整数。

    第四行为山峰数n,0<=n<=50。

    以下共n行,每行首先是一个正整数ui,然后是8个整数,按逆时针方向给出表示山的四边形的顶点坐标。

    输入数据保证A、B两点不会在任何山的内部,四边形任意3个顶点不在同一直线上,所有的整数的绝对值不会大于1000。

    坐标均以整数对的形式给出,第一个数为横坐标,第二个为纵坐标。同一行内若有多个相邻整数,则整数间以至少一个空格隔开。

    输出格式:

    第一行为这个区域山的总面积。

    第二行为设计公路的总长。

    第三行为修建所设计公路的费用。

    输出数据均保留两位小数。

    输入输出样例

    输入样例#1: 复制
    100.00
    21.93
    2252.15
    
    输出样例#1: 复制
    -10 1
    10 1
    100
    2
    110 0 0 -5 5 -10 0 -5 -5
    300 5 -5 10 0 5 5 0 0
    
    提示
    标程仅供做题后或实在无思路时参考。
    请自觉、自律地使用该功能并请对自己的学习负责。
    如果发现恶意抄袭标程,将按照I类违反进行处理。