计算几何：
较常用到的部分包括——线段相交的判断、多边形面积的计算、内点外点的判断、凸包
题目 ZJU1010—面积
题目大意：jerry ，一名中学生，对于数学研究很感兴趣。或许，他思考的问题对专家来说太容易了，但作为一名业余爱好者，特别是一位15岁的孩子，他的确是很棒的。在数学问题上，他思路敏捷，对碰到的问题都能以数学的方式轻易地解决。一天，他在桌子上看到一张纸，是他4岁的妹妹玛丽花的一些线条。他发现这些线条恰好构成一个凹多边形，如下图：
他想“这个多边形好像很规则，我刚刚学过怎样计算三角形，矩形和圆的面积。我肯定能计算这个图形的面积。”他真做起来了，首先标注多边形各顶点的坐标，如下图，然后他很快
我如何计算多边形面积呢？”计算一个随机的多边形面积，他还没有找到一个通用的办法。他知道解决这个问题超出了他的能力。那就帮帮他吧。
输入：
输入数据包含多个图形。每个图形的第一行是一个整数n （0
接下来的n 行，每行是一对实数，表示顶点（xi,yi ）的坐标，坐标是有顺序的，表示从图形的第一个顶点到第二个顶点，从第二个顶点到第三个顶点，直到第n 个顶点。
空的图形（n=0）, 表示输入结束，该图形不必处理。
输出：
对每个图形，输出图形编号，一个冒号，图形的面积或者字符串“impossible ”.
如果该图形是多边形，计算其面积（精确到两位小数）。根据输入的顶点序列，如果不能形成多边形（即一条线与另外一条不相邻的线相交，例如有一个四条线的图形，第一条线与第三条线相交），就输出“impossible ”, 表示这个图形不是多边形。如果给定的顶点数不足以形成多边形，也输出“impossible ”。
每个测试例之间有一个空行。
输入样例：
5
0 0
0 1
0.5 0.5
1 1
1 0
4
0 0
0 1
1 0
1 1
输出样例：
Figure 1：0.75
Figure 2：impossible
机器蛇1922
【问题描述】：在未来的某次战争中，我军计划了一次军事行动，目的是劫持敌人的航母。由于这个计划高度保密，你只知道你所负责的一部分：机器蛇的通信网络。计划中要将数百条机器蛇投放到航母的各个角落里。由于航母内部舱室、管线错综复杂，且大部分由金属构成，因此屏蔽效应十分强烈，况且还要考虑敌人的大强度电子干扰，如何保持机器蛇间的联系，成了一大难题。每条机器蛇的战斗位置由作战计划部门制定，将会及时通知你。每条机器蛇上都带有接收、发射系统，可以同时与多条机器蛇通讯。由于整个系统承载的数据量庞大，需要一个固定的通讯网络。情报部门提供了极其详尽的敌方航母图纸，使你对什么地方有屏蔽了如指掌。
请你设计一个程序，根据以上信息构造通讯网络，要求信息可以在任意两条机器蛇间传递，同时为了避免干扰，通讯网络的总长度要尽可能的短。
【文件输入】：第一行是一个整数n （n≤200）表示参战的机器蛇总数。以下n 行，每行两个整数xi ，yi ，为第i 支机器蛇的战斗位置。接下来一行是一个整数m （m≤100）表示航母内部可能产生屏蔽的位置。最后m 行，每行四个整数ai ，bi ，ci ，di ，表示线段(ai，bi)-(ci，di) 处可能有屏蔽，也就是说通讯网络不能跨越这条线段。
【文件输出】： 仅一个实数，表示建立的通讯网的最短长度，保留3位小数。如果不能成功建立通讯网，请输出-1.000。
【样例输入】：
3
1 3
3 1
5 5
1
0 0 3 3
【样例输出】：8.944
计算几何：
较常用到的部分包括——线段相交的判断、多边形面积的计算、内点外点的判断、凸包
题目 ZJU1010—面积
题目大意：jerry ，一名中学生，对于数学研究很感兴趣。或许，他思考的问题对专家来说太容易了，但作为一名业余爱好者，特别是一位15岁的孩子，他的确是很棒的。在数学问题上，他思路敏捷，对碰到的问题都能以数学的方式轻易地解决。一天，他在桌子上看到一张纸，是他4岁的妹妹玛丽花的一些线条。他发现这些线条恰好构成一个凹多边形，如下图：
他想“这个多边形好像很规则，我刚刚学过怎样计算三角形，矩形和圆的面积。我肯定能计算这个图形的面积。”他真做起来了，首先标注多边形各顶点的坐标，如下图，然后他很快
我如何计算多边形面积呢？”计算一个随机的多边形面积，他还没有找到一个通用的办法。他知道解决这个问题超出了他的能力。那就帮帮他吧。
输入：
输入数据包含多个图形。每个图形的第一行是一个整数n （0
接下来的n 行，每行是一对实数，表示顶点（xi,yi ）的坐标，坐标是有顺序的，表示从图形的第一个顶点到第二个顶点，从第二个顶点到第三个顶点，直到第n 个顶点。
空的图形（n=0）, 表示输入结束，该图形不必处理。
输出：
对每个图形，输出图形编号，一个冒号，图形的面积或者字符串“impossible ”.
如果该图形是多边形，计算其面积（精确到两位小数）。根据输入的顶点序列，如果不能形成多边形（即一条线与另外一条不相邻的线相交，例如有一个四条线的图形，第一条线与第三条线相交），就输出“impossible ”, 表示这个图形不是多边形。如果给定的顶点数不足以形成多边形，也输出“impossible ”。
每个测试例之间有一个空行。
输入样例：
5
0 0
0 1
0.5 0.5
1 1
1 0
4
0 0
0 1
1 0
1 1
输出样例：
Figure 1：0.75
Figure 2：impossible
机器蛇1922
【问题描述】：在未来的某次战争中，我军计划了一次军事行动，目的是劫持敌人的航母。由于这个计划高度保密，你只知道你所负责的一部分：机器蛇的通信网络。计划中要将数百条机器蛇投放到航母的各个角落里。由于航母内部舱室、管线错综复杂，且大部分由金属构成，因此屏蔽效应十分强烈，况且还要考虑敌人的大强度电子干扰，如何保持机器蛇间的联系，成了一大难题。每条机器蛇的战斗位置由作战计划部门制定，将会及时通知你。每条机器蛇上都带有接收、发射系统，可以同时与多条机器蛇通讯。由于整个系统承载的数据量庞大，需要一个固定的通讯网络。情报部门提供了极其详尽的敌方航母图纸，使你对什么地方有屏蔽了如指掌。
请你设计一个程序，根据以上信息构造通讯网络，要求信息可以在任意两条机器蛇间传递，同时为了避免干扰，通讯网络的总长度要尽可能的短。
【文件输入】：第一行是一个整数n （n≤200）表示参战的机器蛇总数。以下n 行，每行两个整数xi ，yi ，为第i 支机器蛇的战斗位置。接下来一行是一个整数m （m≤100）表示航母内部可能产生屏蔽的位置。最后m 行，每行四个整数ai ，bi ，ci ，di ，表示线段(ai，bi)-(ci，di) 处可能有屏蔽，也就是说通讯网络不能跨越这条线段。
【文件输出】： 仅一个实数，表示建立的通讯网的最短长度，保留3位小数。如果不能成功建立通讯网，请输出-1.000。
【样例输入】：
3
1 3
3 1
5 5
1
0 0 3 3
【样例输出】：8.944