数学 - 好孩子's Blog

判断两条线段是否有交点

#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;
}