863软件园杯第一届河南省大学生程序设计竞赛(正式比赛试题)主办：河南省计算机学会承办：郑州大学信息工程学院协办：YOCSEF郑州分论坛地点：郑州大学南校区软件学院时间：2008年5月18日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【样例】【试题二】据不完全统计，受地震影响，四川大部分灾区通信陷入瘫痪，数千个基站因断电、传输中断等原因退出服务，目前总公司已紧急部署对受灾地区进行通信抢修。
按照应急通信保障预案，必须尽快、付出代价最小，效率更高来全力恢复通信。
由于四川大部分灾区都处于山区，有很多基站之间不能直接建立通信。
现已知建立各基站之间直接通信的代价，问如何建立总代价最小的通信网，使得任意两个基站之间都能通信？【标准输入】第1行：N(N为的个数)第2~N+1行：Pi1 Pi2 ……Pin（Pij为建立基站i与基站j直接通信的代价i, j=1 , 2, …., N ）【标准输出】T（建立通信网的最小代价数）【约束条件】（1）10 ≤N≤1000（2） -1 ≤Pij ≤ 1000 Pij为整数，若Pij = -1，表示基站i与基站j不能直接通信（3）时间限制：1000MS【样例】#define N 1000#define inf 1001#define true 1#define false 0#include “stdio.h”int p[N+1][N+1];//======================================long Prim(int n ){ long T=0; int i, j, k ,s[N+1];int lowcost[N+1], closest[N+1];s[1]=true;//先选择顶点1for(i=2; i<=n; ++i){ lowcost[i]=p[i][1]; closest[i]=1; s[i]= false; } for(i=1; i<n; ++i) //循环n-1次{ int min=inf; //设inf为无穷大j=1;for(k=2; k<=n; ++k)if((!s[k])&&(lowcost[k]<min)){ min=lowcost[k]; j=k; }//prinf(“%d %d \n” , j , closest[j] );T+=p[j][ closest[j] ]; s[j]=true;for(k=2; k<=n; ++k) //调整未加入顶点的最小边if ((!s[k])&&(p[k][j]<lowcost[k])){ lowcost[k]=p[k][j] closest[k]=j; }}return T; }//============================int main( ){ int i, j, n ; long T;scanf(“%d\n”,&n);for(i=1; i<=n; i++)for(j=1;j<=n; j++){ scanf(“%d”,&p[i][j];if (p[i][j]<=0) p[i][j]=1001; }T=Prim(n);Printf(“ld”,T);}//参见<<算法设计与分析>> P117密码破译某组织欲破获一个外星人的密码，密码由一定长度的字串组成。
![[信息与通信]第三届“ZLG杯”大学生FPGADIY创新电子设计竞赛获奖作品论文集](https://img.taocdn.com/s1/m/f299450aa31614791711cc7931b765ce05087aee.png)
