COJ 1645计算几何：判断线段是否相交 - c++编程基础

线段相交

Time Limit: 1000 ms Memory Limit: 10000 KB
Total Submit: 191 Accepted: 46
Description 给你两个线段，已知它们的端点，判断它们是否有交点。
Input 第一行：x1,y1,x2,y2,代表第一条线段的两个端点；
第二行：x3,y3,x4,y4,代表第二条线段的两个端点； ps:所有数据为整数，绝对值不超过1000.
Output 如果有交点，输出“Y”，否则输出“N”。
Sample Input 0 0 1 1

0 1 1 0
Sample Output Y
Hint 计算几何小练习
Source antry

#include 
  
   
#include 
   
     #include 
    
      #include 
     
       #include 
      
        #include 
       
         #include 
        
          #include 
         
           #include 
          
            #include 
           
             #include 
            
              #include 
              #include 
              
                #include 
               
                 #define PI acos(-1.0) #define eps 1e-8 #define mem(a,b) memset(a,b,sizeof(a)) #define sca(a) scanf("%d",&a) #define pri(a) printf("%d\n",a) #define f(i,a,n) for(i=a;i
                
                  eps;} struct Point{ double x, y; Point(const double &x = 0, const double &y = 0):x(x), y(y){} Point operator - (const Point &a)const{ return Point(x - a.x, y - a.y);} Point operator + (const Point &a)const{ return Point(x + a.x, y + a.y);} Point operator * (const double &a)const{ return Point(x * a, y * a);} Point operator / (const double &a)const{ return Point(x / a, y / a);} bool operator < (const Point &a)const{ return sgn(x - a.x) < 0 || (sgn(x - a.x) == 0 && sgn(y - a.y) < 0);} friend double det(const Point &a, const Point &b){ return a.x * b.y - a.y * b.x;} friend double dot(const Point &a, const Point &b){ return a.x * b.x + a.y * b.y;} friend double dist(const Point &a, const Point &b){ return sqrt(sqr(a.x - b.x) + sqr(a.y - b.y));} double len(){ return sqrt(dot(*this, *this));} Point rotateA(const double &angle)const{ return rotateS(cos(angle), sin(angle));} Point rotateS(const double &cosa, const double &sina)const{ return Point(x * cosa - y * sina, x * sina + y * cosa);} void in(){ scanf("%lf %lf", &x, &y); } void out()const{ printf("%.2f %.2f\n",x, y);} }; struct Line{ Point s, t; Line(const Point &s = Point(), const Point &t = Point()):s(s), t(t){} Point dire()const{ return t - s;} double len()const{ return dire().len();} bool isPointInLine(const Point &p)const{ return sgn(det(p - s, t - s)) == 0 && sgn(dot(p - s, p - t)) <= 0;} bool isPointInLineEx(const Point &p)const{ return sgn(det(p - s, t - s)) == 0 && sgn(dot(p - s, p - t)) < 0;}//不含端点 Point pointProjLine(const Point &p){ return s + dire() * ((dot(p - s, dire()) / dire().len()) /(dire().len()));} double pointDistLine(const Point &p){ return fabs(det(p - s, dire()) / dire().len());} friend bool sameSide(const Line &line , const Point &a, const Point &b){ return sgn(det(b - line.s, line.dire())) * sgn(det(a - line.s, line.dire())) > 0; } friend bool isLineInsectLine(const Line &l1, const Line &l2){ if(sgn(det(l2.s - l1.s, l1.dire())) == 0 && sgn(det(l2.t - l1.s, l1.dire())) == 0 && sgn(det(l1.s - l2.s, l2.dire())) == 0 && sgn(det(l1.t - l2.s, l2.dire())) == 0){ return l1.isPointInLine(l2.s) || l1.isPointInLine(l2.t) || l2.isPointInLine(l1.s) ||l2.isPointInLine(l1.t); } return !sameSide(l1, l2.s, l2.t) && !sameSide(l2, l1.s, l1.t); } friend Point lineInsectLine(const Line &l1, const Line &l2){ double s1 = det(l1.s - l2.s, l2.dire()), s2 = det(l1.t - l2.s, l2.dire()); return (l1.t * s1 - l1.s * s2) / (s1 - s2); } void in(){ s.in(); t.in();} void out()const{ s.out(); t.out(); } }; int main() { Point a,b,c,d; cin>>a.x>>a.y>>b.x>>b.y>>c.x>>c.y>>d.x>>d.y; Line a1,b1; a1.s=a,a1.t=b,b1.s=c,b1.t=d; if(isLineInsectLine(a1,b1)) puts("Y"); else puts("N"); return 0; }