判断两条线段是否有交点
#include<iostream>
using namespace std;
typedef struct node
{
double x;
double y;
}Node;
Node star[100],end[100];
int max_dian,N; //N条直线;
double max(double a,double b)
{
return a>b?a:b;
}
double min(double a,double b)
{
return a<b?a:b;
}
double Direction(Node p1,Node p2,Node p) //判断p与线段p1p2 的位置关系,p1当作"原点";
{
return (p2.x-p1.x)*(p.y-p1.y)-(p.x-p1.x)*(p2.y-p1.y);
}
bool online(Node p1,Node p2,Node p) //判断p是否在p1p2上;
{
double max=p1.y>p2.y?p1.y:p2.y;
double min=p1.y>p2.y?p2.y:p1.y;
if( p.y>=min && p.y<=max ) return true;
return false;
}
bool cross(Node p1,Node p2,Node p3,Node p4)
{
double d1=Direction(p1,p2,p3);
double d2=Direction(p1,p2,p4);
double d3=Direction(p3,p4,p1);
double d4=Direction(p3,p4,p2);
if( d1*d2<0 && d3*d4<0 ) return true;
if( d1==0 && online(p1,p2,p3)) return true;//d1=0说明p3在p1_p2上, ;
if( d2==0 && online(p1,p2,p4)) return true;//还要判断是否在线段上
if( d3==0 && online(p3,p4,p1)) return true;
if( d4==0 && online(p3,p4,p2)) return true;
return false;
}
void find_set()
{
max_dian=0;
for(int i=1;i<=N;i++)
{
for(int j=i+1;j<=N;j++)
{
if(cross(star[i],end[i],star[j],end[j]))
max_dian++;
}
}
printf("%d\n",max_dian);
}
int main()
{
freopen("D:\\in.txt","r",stdin);
while( scanf("%d",&N),N)
{
for(int i=1;i<=N;i++)
{
scanf("%lf%lf%lf%lf",&star[i].x,&star[i].y,&end[i].x, &end[i].y);
}
find_set();
}
return 0;
}