題意：求一堆線段兩兩相交的次數，即使交點重疊也算在內
更詳細的幾何講解：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
C++代碼
#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;
}
