HDu 1086 You can Solve a Geometry Problem too(2つのセグメントが交差しているかどうかを判断)

You can Solve a Geometry Problem too
Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 65536/32768 K (Java/Others)
Total Submission(s): 9195    Accepted Submission(s): 4498
Problem Description
Many geometry(幾何学)problems were designed in the ACM/ICCC.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.00 0 
   
 
  

解析：http://dev.gameres.com/Program/Abstract/Geometry.htm#判断两线段是否相交
                 需要注意的是，在做跨立实验的时候，需要同时满足 L1的两个端点在L2两端，L2的两个端点在 L1 两端。
           比如这组数据：
           2
           -1.00 0.00 1.00 1.00
          1.0 0.0 2.0 0.0
代码：

#include
#include
using namespace std;

const int maxn=1e2;
struct tnode{
    double x,y;
}a[maxn*2+10];

bool ok(int i,int j)
{
  if(min(a[i].x,a[i+1].x)>max(a[j].x,a[j+1].x))return 0;
  if(max(a[i].x,a[i+1].x)max(a[j].y,a[j+1].y))return 0;
  if(max(a[i].y,a[i+1].y)0)return 0; 

  x1=a[i+1].x-a[i].x,y1=a[i+1].y-a[i].y;
  x3=a[j+1].x-a[i].x,y3=a[j+1].y-a[i].y;
  x2=a[j].x-a[i].x,y2=a[j].y-a[i].y;
  return (x1*y2-x2*y1)*(x1*y3-x3*y1)<=0;
}

int main()
{
  //freopen("1.in","r",stdin);
  
  int n,i,j,ans;
  while(scanf("%d",&n),n)
    {
      for(n*=2,i=1;i<=n;i++)
        scanf("%lf%lf",&a[i].x,&a[i].y);
      for(ans=0,i=1;i<=n;i+=2)
        for(j=i+2;j<=n;j+=2)ans+=ok(i,j);
      printf("%d
",ans);
    }
  return 0;
}