第一届河南省大学生程序设计竞赛(正式赛)

863 软件园杯 第一届河南省大学生程序设计竞赛 (正式比赛试题) 主办：河南省计算机学会 承办：郑州大学信息工程学院 协办：YOCSEF郑州分论坛 地点：郑州大学南校区软件学院 时间：2008年 5月 18日 考试时间： 5 小时（9： 00 ~ 14： 00） 分数分布：共8 题，满分800 分。 文件命名：程序文件名为：T 题号。如第二题应提交：T2.c 5 月 12 日 14 时 28 分，四川汶川县发生了7.8 级地震。突如其来的地震灾害，把全国人民和灾区人民的心紧紧连在一起。中共中央政治局常务委员会召开会议，全面部署当前抗震救灾工作。会议强调，灾情就是命令，时间就是生命。各有关部门一定要紧急行动起来，把抗震救灾作为当前的首要任务，一方有难、八方支援，想一想，我们选手能为灾区做点什么？ 【试题一】 灾区已经非常困难，灾民需要帐篷、衣物、食品和血浆。可通往灾区的道路到处都是塌方，70%以上的路面损坏，桥梁全部被毁。中国空军立即启动应急预案，展开史上最大强度非作战空运行动，准备向灾区空投急需物资。由于余震不断，天气恶劣，怎样知道空投的物资是否落在某灾区的区域内呢？ 经过空中观测，某灾区为一凸多边形，空投的物资落在P(X,Y)点。你能否给出一个正确判断？ 【 标准输入】 第 1 行： N X Y (N 为凸形的边数，X， Y 为空投物资的坐标 ) 第 2 行： X1 Y1 X2 Y2…….Xn Yn （逆序给出的N 个顶点坐标 ） 【 标准输出】 YES （物资落在灾区的区域内 ） 或 NO （物资落在灾区的区域外 ） 【 约束条件】 （ 1） 3 ≤ N ≤ 20 （ 2） 所有的坐标Xi 和 Yi 为整数 -10000≤ Xi ， Yi ≤ 10000 （ 3） X,Y 为整数 -10000≤ X ， Y ≤ 10000 （ 4） 时间限制： 1000MS 【 样 例 】 标准输入 标准输出 4 2 2 YES -1 0 3 -2 10 9 -1 110 【试题二】 据不完全统计，受地震影响，四川大部分灾区通信陷入瘫痪，数千个基站因断电、传输中断等原因退出服务，目前总公司已紧急部署对受灾地区进行通信抢修。按照应急通信保障预案，必须尽快、付出代价最小，效率更高来全力恢复通信。 由于四川大部分灾区都处于山区，有很多基站之间不能直接建立通信。现已知建立各基站之间直接通信的代价，问如何建立总代价最小的通信网，使得任意两个基站之间都能通信？ 【 标准输入】 第 1 行： N (N 为的个数 ) 第 2~ N+1 行： Pi1 P...