# 計算幾何

模板

struct point{
    ll x, y;
    point operator+(point p1){
        return point{x+p1.x, y+p1.y};
    }
    point operator-(point p1){
        return point{x-p1.x, y-p1.y};
    }
    ll operator^(point p1){
        return x*p1.y-p1.x*y;
    }
    ll operator*(point p1){
        return x*p1.x+y*p1.y;
    }
};
 
bool onseg(point p1, point p2, point p3){
    point a=p1-p3, b=p2-p3;
    return (a^b)==0 && (a*b)<=0;
}
 
int sign(ll num){
    if(num<0) return -1;
    else if(num>0) return 1;
    return 0;
}
 
bool banana(point p1, point p2, point q1, point q2){
    if(onseg(p1, p2, q1) || onseg(p1, p2, q2) ||
        onseg(q1, q2, p1) || onseg(q1, q2, p2)) return true;
    if(sign((p2-p1)^(q1-p1))*sign((p2-p1)^(q2-p1))<0 &&
        sign((q2-q1)^(p1-q1))*sign((q2-q1)^(p2-q1))<0) return true;
    return false;
}