转载：http://blog.csdn.net/freezhanacmore/article/details/7905282
用线段划分平面（实质线段相交问题）
原题链接：http://acm.fzu.edu.cn/problem.php?pid=1015
来源：CSUST组织的多校联合组队赛第一场D题列强瓜分。2012年8月5日12:00到17:00
Problem 1015 土地划分
Problem Description
在Dukeswood这块土地上生活着一个富有的农庄主和他的几个孩子。在他临终时，他想把他的土地分给他的孩子。他有许多农场，每个农场都是一块矩形土地。他在农场地图上划上一些直线将矩形分成若干块。当他划直线时，他总是从矩形边界上的某一点划到另一个矩形边界上的点，这条线的结束点将成为下一条线的起始点。他划线时从不会让任三线共点。例如图1是某一种划分结果。
图1
划分的起始点和结束点均以五角星标记。当他完成划分后，他想要数一下划出的土地的块数以确保每个孩子都有一块地。例如，图1中土地被划分成18块。然而这个庄主由于年迈常会数错，因而他寻求你的帮助。
请写一个程序，输入原来的土地尺寸及线段的位置，输出划分出的土地块数。
Input
第一行输入地图的宽度w (1<=w<=1000)和高度 h (1<=h<=1000)，均为整数。
第二行输入线段数L (1<=L<=50)。
以下L+1行每行一个整数坐标(Xi,Yi)，庄主划的线段为(Xi,Yi)-(Xi+1,Yi+1)，i=1,2,…,L。当然(Xi,Yi)必定在矩形的边界上。
最后一组数据w=h=0，标志文件结束，不需要处理。
Output
Sample Input
Sample Output
//思路：最终的结果ans=L+dot+1 L 表示给出的线段数、dot代表点的数目
/*(因为开始的3个点，会把平面分成3个面且中间无交点，后来从第四个点，
也就是第三条线开始每出现一个点，就会多出一个平面，但是多了一条线同样也会多出一个平面
所以最终的结果就是求所以的点的个数，包括端点和交点
注意：起点和终点重合问题。（重合一次就多算一个点，但是在程序中算在交点中了，所以就不用再加了）
// 题目关键:求交点个数(即判断线段是否相交)，利用跨立试验
如果线段P1P2和直线Q1Q2相交，则P1P2跨立Q1Q2，
即：( P1 - Q1 )×( Q2 - Q1 )*( Q2 - Q1 )×( P2 - Q1 )>=0。
有关跨立实验详解，见我的另外一篇博客：http://blog.csdn.net/cfreezhan/article/details/7894751
*///
// AC 0ms 192kb (by C++ on FZU 1015)
#include<stdio.h>
int main()
{
int w,h,l;
int x[55],y[55];
int i;
int ans;
while(scanf("%d%d",&w,&h)!=EOF && w!=0 && h!=0)
{
ans=3; //开始若有两条线则必定把矩形分成3块，且中间没有交点
scanf("%d\n",&l);
for(i=0;i<=l;i++)
scanf("%d%d",&x[i],&y[i]);
if(l<3) //当矩形中的线段小于三条时，分得的面积，就是线段数加上1;
{
ans=l+1;
printf("%d\n",ans);
continue;
}
else
{
for(i=3;i<=l;i++) //当矩形中的线段大于三条时，没多出一条线，就会多出一个面，然后多出的这条线与前面所有的线像比，若多出一个交点则，多出一个面
{
ans++;
int k=i-2;
while(k>0) //跨立试验，利用叉积判断是否相交 （网上N多代码都判断了两次，貌似只用判断一次就行了，因为不会出现跨立不相交的情况）
{
int s1=(x[i-1]-x[k-1])*(y[k]-y[k-1])-(y[i-1]-y[k-1])*(x[k]-x[k-1]);
int s2=(x[k]-x[k-1])*(y[i]-y[k-1])-(y[k]-y[k-1])*(x[i]-x[k-1]);
if(s1*s2>0)
ans++;
k--;
}
}
}
printf("%d\n",ans);
}
return 0;
}