【判线段相交】HDU 1086

基德KID.1412

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 __int64struct 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.s.x, &l.s.y, &l.e.x, &l.e.y);res = 0;for (i = 0; i < n; i++)for (j = i + 1; j < n; j++)if (intersect (l, l[j]))res++;printf ("%d\n", res);}return 0;}