[線分交点]0807

テンプレートでは、ポイントがチャーシューを求める過程でオーバーフローする可能性があります.解決方法はdoubleを使用します.
doubleを使う:

# include <cmath>



const double eps = 1e-8;



struct Point{double x, y;} ;



int dcmp(double x)

{

    if (fabs(x) < eps) return 0;

    return x>0 ? 1:-1;

}



int direction(Point p1, Point p2, Point p3)

{

    double tmp = (p3.x-p1.x)*(p2.y-p1.y) - (p2.x-p1.x)*(p3.y-p1.y);

    return dcmp(tmp);

}



char isCross(Point p1, Point p2, Point p3, Point p4)

{

    int d1 = direction(p3, p4, p1);

    int d2 = direction(p3, p4, p2);

    int d3 = direction(p1, p2, p3);

    int d4 = direction(p1, p2, p4);

    if (d1*d2 < 0 && d3*d4 < 0) return 1;

    return 0;

}

intを使って符号を返す:

struct Point{int x, y;} ;

  

int direction(Point p1, Point p2, Point p3)

{

    int tmp = (p3.x-p1.x)*(p2.y-p1.y) - (p2.x-p1.x)*(p3.y-p1.y);

    if (tmp == 0) return 0;

    return tmp>0 ? 1:-1;

}

  

char isCross(Point p1, Point p2, Point p3, Point p4)

{

    int d1 = direction(p3, p4, p1);

    int d2 = direction(p3, p4, p2);

    int d3 = direction(p1, p2, p3);

    int d4 = direction(p1, p2, p4);

    if (d1*d2 < 0 && d3*d4 < 0) return 1;

    return 0;

}