SGOI第三次竞赛试题

　　要求：初中组SG1、SG2、SG5必做,高中组全做

　　每题存盘文件名分别为：sg1.pas,sg2.pas,sg3.pas,sg4.pas,sg5.pas

　　所有题目的输入文件为sgin.txt输出文件为sgou.txt SG1

　　电话局选址 在一个山区乡镇里，分布着若干个村庄(n<10)。这个镇计划筹建一个电话模块网，在这一模块网中每个村庄被连接到一起，村庄与村庄之间只用一条电缆连接，并且除了首尾的两个村庄只分别连接着一个村庄外，其他的任一个村庄恰连接着两个村庄。图1给出了各个村庄的分布情况，图中已标出了各个村庄的坐标，连接各村庄的直线距离单位为千米。

　　你的任务是选择一个村庄作为电话模块网的起点，希望埋设的电缆线长度尽可能的短。

　　1.输入

　　输入文件由若干行数据序列组成，第一行，一个数据表示村庄的个数；第二行开始，每行两个数据，数据之间用一个或若干个空格隔开，用以表示每个村庄的坐标。镇中心的坐标即为坐标中心。

　　2.输出

　　输出结果的第一行为该电话模块网中起点村庄的坐标；以下第i行数据是第i个是村庄的坐标，最后一行是一个数据，即：耗用电缆长度的最小值。

　　3.输入、输出样例：

　　SG2 海上搜索 在南海的某一海面内岛屿和海洋交错衡生,进行海上搜索作业，先对搜索区域的海洋图分割成若干个M×N大小相同的网格,其中M（M<50）表示行,N(N<50)表示列,在网格中以1表示海洋,0表示岛屿（位于纵向或横向相邻的成片数字视为一个岛屿）如图1有3个岛屿，图2有1 个岛屿。

　　你的任务是为这次的海上搜索作业确定一个基准区域，所谓的基准区域是指如上图的图像中的一块矩形区域：

　　（1）每一个岛屿都有部分面积（网格）在此区域内；

　　（2）在满足（1）的条件下，区域面积最小。

　　一幅图像中的基准区域可能不是唯一的，但各基准区域面积必定是相同的。

　　根据给定的图像，确定其基准区域的面积。

　　输入数据：输入文件的第一行有两个整数M和N，中间用一个空格分隔。随后有M行，每行有N个数字（0和1），数字间用一个空格分隔，构成M×N的网格。

　　输出数据：输出文件的第一行为基准区域的面积，即基准区域的网格数。
　　输入输出样例：

　　SG3 获取学分 学校实行学分制。每门的必修课都有固定的学分，同时还必须获得相应的选修课程学分。学校开设了N（N<300）门的选修课程，每个学生可选课程的数量M是给定的。学生选修了这M门课并考核通过就能获得相应的学分。

　　在选修课程中，有些课程可以直接选修，有些课程需要一定的基础知识，必须在选了其它的一些课程的基础上才能选修。例如《Frontpage》必须在选修了《Windows操作基础》之后才能选修。我们称《Windows操作基础》是《Frontpage》的先修课。每门课的直接先修课最多只有一门。两门课也可能存在相同的先修课。每门课都有一个课号，依次为1，2，3，…。 例如:

　　表中1是2的先修课，2是3、4的先修课。如果要选3，那么1和2都一定已被选修过。 　　你的任务是为自己确定一个选课方案，使得你能得到的学分最多，并且必须满足先修课优先的原则。假定课程之间不存在时间上的冲突。

　　输入数据：输入文件的第一行包括两个整数N、M（中间用一个空格隔开）其中1≤N≤300,1≤M≤N。

　　以下N行每行代表一门课。课号依次为1，2，…，N。每行有两个数（用一个空格隔开），第一个数为这门课先修课的课号（若不存在先修课则该项为0），第二个数为这门课的学分。学分是不超过10的正整数。

　　输出数据：输出文件每行只有一个数。第一行是实际所选课程的学分总数。以下各行的数，表示所选课程的课号。

　　输入输出样例：

　　SG4 求交集多边形面积 在平面上有两给定的凸多边形，若两凸多边形相交，则它们的交集也是一个凸多边形。若两凸多边形不相交，指的是两凸多边形相离或仅限于边界点与边上相交，则相交面积为0。如图所示： 你的任务是编程给出交集多边形的面积。

　　两给定的凸多边形按顺时针方向依次给出多边形每个顶点的坐标。

　输入数据：输入文件第一行为一整数M，表示第一个凸多边形的边数，以后M行分别给出了M个顶点的坐标；接着，给出第二个凸多边形的边数N，以后N行分别给出了N个顶点的坐标。

　　输出数据：只一个数据即交集面积，保留两位小数点。

　　输入输出样例：

　　SG5 组数问题 一集合有M个（M≤50）数，把其中末位数或首位数相等的两个数相加，组成一个新的数使其和最大(如：9 99 999三个数，则应选择后面两个相加)。

　　你的任务是找出符合条件的新数，并统计输出该集合至多有的N个新数。每一个输入的数位长m≤100，输出的数位长不限，要完整地输出。

　　例如：

　　M=7
　　13089
　　20873909
　　35763
　　987637275
　　999
　　30987656284367493274567595
　　1000000101010101010101010101010100000 则可以组成： 　　1000000101010101010101010101010113089 {首位为1}

　　30987656284367494262204870 {末位为5} 等共有5个新数。

　　输入数据：输入文件的第一行为输入数的个数，以下各行为各输入数。

　　输出数据：输出文件的第一行为至多能组成新数的个数，以下各行为组成的新数。

　　输入输出样例：