알고리즘이 맞는거 같은데 live archive에서 계속 WA를 뱉어내서
힘드네요..ㅠㅠ

https://icpcarchive.ecs.baylor.edu/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=2254

일단 알고리즘은 모든 페어마다 엑스자로 y=0과 만나는 구간을 생성해서 이러한 페어마다의 구간(n^2개)의 교집합이 있는지 없는지를 체크하는 알고리즘인데요..

맞는 알고리즘인거같은데 계속 틀리네요. 기본적으로 n^2으로 걍 돌리면 TLE가 나오길래 도중에 커팅 코드를 집어넣엇는데 아무래도 double 타입 오차범위때문에 이러는거같은데 고칠수가 없네요 ㅠㅠ 유리수로 해봤는데 생각해보니x절편 구할때 분모에 10^{14정도까지} 올라가서 비교함수에서 곱셈 연산에서 overflow가 나서 long long타입으로 유리수를 줘도 안되고.. gcd로 분모분자 낮추는 코드를 집어넣으면 TLE가 나고.. 그렇다고 bignum으로 하자니 또 TLE 날꺼같고 ㅠㅠ 도와주세요..

#define EPS 1e-9

struct Line {
    int y,x1,x2;
    Line(){}
    Line(int a, int b, int c) : y(a), x1(b), x2(c) {}
    bool operator < (const Line &a) const {
        return y < a.y;
    }
} L[5005];

int T,n,W;

double calc(double x1, double y1, double x2, double y2) {
    double A = y1 - y2;
    double B = x2 - x1;
    double C = -(A*x1+B*y1);
    return -C / A;
}

int main() {
#ifdef LOCAL
    freopen("in.txt","r",stdin);
#endif
    scanf("%d",&T);
    while(T--) {
        scanf("%d%d",&W,&n);
        for(int i=0;i<n;++i) {
            int y,x1,x2; scanf("%d%d%d",&y,&x1,&x2);
            L[i] = Line(y,x1,x2);
        } sort(L, L + n);

        double s = 0, e = W;
        for(int i=0;i<n;++i) for(int j=i+1;j<n;++j) {
            s = max(s,calc(L[i].x1,L[i].y,L[j].x2,L[j].y));
            e = min(e,calc(L[i].x2,L[i].y,L[j].x1,L[j].y));
            if(s - EPS> e) break;
        }
        if(s - EPS > e) cout<<"NO"<<endl;
        else cout<<"YES"<<endl;
    }
}