学步园

Many geometry（几何）problems were designed in the ACM/ICPC. And now, I also prepare a geometry problem for this final exam. According to the experience of many ACMers, geometry problems are always much trouble, but this problem is very
easy, after all we are now attending an exam, not a contest
Give you N (1<=N<=100) segments（线段）, please output the number of all intersections（交点）. You should count repeatedly if M (M>2) segments intersect at the same point.
Note:
You can assume that two segments would not intersect at more than one point.
Input

Input contains multiple test cases. Each test case contains a integer N (1=N<=100) in a line first, and then N lines follow. Each line describes one segment with four float values x1, y1, x2, y2 which are coordinates of the segment’s
ending.
A test case starting with 0 terminates the input and this test case is not to be processed.
Output

For each case, print the number of intersections, and one line one case.
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.0
0

1
3

(1)快速排斥试验
　　　　设以线段P1P2为对角线的矩形为R，设以线段Q1Q2为对角线的矩形为T，如果R和T不相交，显然两线段不会相交。
(2)跨立试验如果两线段相交，则两线段必然相互跨立对方。若P1P2跨立Q1Q2，则矢量
(P1 - Q1 ) 和( P2 - Q1 )位于矢量( Q2 - Q1 )的两侧，

即            ( P1 - Q1 ) × ( Q2 - Q1 ) * ( P2 - Q1 ) × ( Q2 - Q1 ) < 0。

上式可改写成  ( P1 - Q1 ) × ( Q2 - Q1 ) * ( Q2 - Q1 ) × ( P2 - Q1 ) > 0。

当 ( P1 - Q1 ) × ( Q2 - Q1 ) = 0时，说明 (P1 - Q1 )和
( Q2 - Q1 )共线，但是因为已经通过快速排斥试验，所以P1一定在线段Q1Q2上；

同理，( Q2 - Q1 ) ×(P2 - Q1 ) = 0说明P2
一定在线段Q1Q2上。

 

所以判断P1P2跨立Q1Q2依据是：( P1 -Q1 ) × (Q2 - Q1 ) * (
Q2 - Q1 ) × ( P2 - Q1 ) >= 0。

同理判断Q1Q2跨立P1P2依据是：( Q1 -P1 ) × ( P2 - P1 ) * (
P2 - P1 ) × ( Q2 - P1 ) >= 0。

上面的算法在两线段共线时会有问题，这时第二步时两个叉积都为0，这时就可以用这四个点的不相等的坐标分量来判断两线段是否有重合部分就行了。如果X、Y坐标分量都相等，那就是一个点了……  
    
  此外在用叉积作判断时认为一个线段的端点点在另一个线段上或两线线段有公共端点时两线段有交点。如果这种情况认为是无交点，则加上对叉积结果是否为0的判断，只要有0出现就认为是无交点，不需要对共线情况特殊处理。

 

#include<iostream>
using namespace std;
#include<stdio.h>
#include<math.h>

struct Point
{
    double x1,y1,x2,y2;
} point[110];
int intersection(Point a,Point b)
{
    if(((a.x1-b.x1)*(a.y2-b.y1)-(a.x2-b.x1)*(a.y1-b.y1))*((a.x1-b.x2)*(a.y2-b.y2)-(a.x2-b.x2)*(a.y1-b.y2))>0)return 0;
    if(((b.x1-a.x1)*(b.y2-a.y1)-(b.x2-a.x1)*(b.y1-a.y1))*((b.x1-a.x2)*(b.y2-a.y2)-(b.x2-a.x2)*(b.y1-a.y2))>0)return 0;
    return 1;
}
int main()
{
    int n,count;
    while(scanf("%d",&n),n)
    {
        for(int i=0; i<n; i++)
            scanf("%lf%lf%lf%lf",&point[i].x1,&point[i].y1,&point[i].x2,&point[i].y2);
        count =0;
       for(int i=0;i<n;i++)
        for(int j=i+1;j<n;j++)
             if(   intersection(point[i],point[j])  )   count++;
        printf("%d\n",count);
    }
    return 0;
}