【判线段相交】HDU 1086

http://acm.hdu.edu.cn/showproblem.php?pid=1086

题意：求一堆线段两两相交的次数，即使交点重叠也算在内
更详细的几何讲解：http://dev.gameres.com/Program/Abstract/Geometry.htm#判断两线段是否相交

Sample Input
2
0.00 0.00 1.00 1.00
0.00 1.00 1.00 0.00
3
0.00 0.00 1.00 1.00
0.00 1.00 1.00 0.000
0.00 0.00 1.00 0.00
0

Sample Output
1
3

#include <iostream>
#include <fstream>
#include <algorithm>
#include <string>
#include <set>
//#include <map>
#include <queue>
#include <utility>
#include <iomanip>
#include <stack>
#include <list>
#include <vector>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <ctime>
#include <ctype.h>
using namespace std;
#define L __int64

struct point{    //点结构
	double x, y;
	point (double a = 0, double b = 0) {x = a, y = b;}
};

struct line{    //线段结构
	point s, e;
	line (point a, point b) {s = a, e = b;}
	line (){}
}l[105];

double multi (point a, point b, point c)    //叉积判断点线关系
{
	double x1, y1, x2, y2;
	x1 = b.x - a.x;
	y1 = b.y - a.y;
	x2 = c.x - b.x;
	y2 = c.y - b.y;
	return x1*y2 - x2*y1;
}

bool intersect (line a, line b)    //判断两线段是否相交
{
	if (max (a.s.x, a.e.x) >= min (b.s.x, b.e.x) &&    //快速排斥试验
		max (b.s.x, b.e.x) >= min (a.s.x, a.e.x) &&
		max (a.s.y, a.e.y) >= min (b.s.y, b.e.y) &&
		max (b.s.y, b.e.y) >= min (a.s.y, a.e.y) &&
		multi (a.s, b.s, b.e)*multi (a.e, b.s, b.e) <= 0 &&    //跨立试验
		multi (b.s, a.s, a.e)*multi (b.e, a.s, a.e) <= 0)
		return true;
	return false;
}

int main()
{
	int n, i, res, j;
	while (scanf ("%d", &n), n)
	{
		for (i = 0; i < n; i++)
			scanf ("%lf%lf%lf%lf", &l[i].s.x, &l[i].s.y, &l[i].e.x, &l[i].e.y);
		res = 0;
		for (i = 0; i < n; i++)
			for (j = i + 1; j < n; j++)
				if (intersect (l[i], l[j]))
					res++;
		printf ("%d\n", res);
	}
	return 0;
}