程式師世界 >> 編程語言 >> C語言 >> C++ >> C++入門知識 >> COJ 1645計算幾何：判斷線段是否相交

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