//hdu1086 求n个线段相交点数量。。.
//http://acm.hdu.edu.cn/showproblem.php?pid=1086
//以下为翻译后的tip：
//给您N（1 <= N <= 100）个细分（线段），请输出所有交叉点的数量。如果M（M> 2）个线段在同一点相交，则应重复计算。
//您可以假设两个线段相交的点不会超过一个。(不重合)
// 解法很一般：遍历每两条线段，判断是否有交点。
//判断两直线是否相交的办法：两直线联立。求交点坐标。。。
// 高中知识，不要记忆，直接推导即可。
//直线一般式方程：(y2 - y1) * x + (x1 - x2) * y + (x2 * y1 - x1 * y2) = 0; 原式（A*x + B*y + C = 0）
//交点坐标 x: (b1 * c2 - b2 * c1) / (a1 * b2 - a2 * b1) , y: (a2 * c1 - a1 * c2) / (a1 * b2 - a2 * b1);
//如果 a1 * b2 - a2 * b1 == 0 则表示没有交点(平行)
1 #include<cstdio> 2 3 struct Line { 4 double x1, y1, x2, y2; 5 } line[105]; 6 7 int n; 8 9 bool intersect(int l1, int l2) { 10 double a1 = line[l1].y2 - line[l1].y1; 11 double b1 = line[l1].x1 - line[l1].x2; 12 double c1 = line[l1].x2*line[l1].y1 - line[l1].x1*line[l1].y2; 13 double a2 = line[l2].y2 - line[l2].y1; 14 double b2 = line[l2].x1 - line[l2].x2; 15 double c2 = line[l2].x2*line[l2].y1 - line[l2].x1*line[l2].y2; 16 if(a1*b2 - a2*b1 == 0) return false; 17 double x = (b1*c2 - b2*c1)/(a1*b2 - a2*b1); 18 double y = (a2*c1 - a1*c2)/(a1*b2 - a2*b1); 19 if((x >= line[l1].x1 && x <= line[l1].x2 || x <= line[l1].x1 && x >= line[l1].x2) 20 && (x >= line[l2].x1 && x <= line[l2].x2 || x <= line[l2].x1 && x >= line[l2].x2)) return true; 21 return false; 22 } 23 24 int main() { 25 while(scanf("%d", &n) == 1 && n) { 26 for(int i = 0; i != n; ++i) { 27 scanf("%lf%lf%lf%lf", &line[i].x1, &line[i].y1, &line[i].x2, &line[i].y2); 28 } 29 int ans = 0; 30 for(int i = 0; i != n-1; ++i) { 31 for(int j = i+1; j != n; ++j) { 32 if(intersect(i, j)) ans++; 33 } 34 } 35 printf("%d\n", ans); 36 } 37 return 0; 38 }