이 문제는 6번째로 많이 풀린 문제로 14팀이 풀었습니다.
동경대의 __________(andaasukoaazu)팀이 40분만에 최초로 풀었네요. (ㅎㄷㄷ)
푼 팀의 수나 최초로 풀린 시간으로 볼 때, 역시 그리 어려운 문제는 아니었습니다.
문제 설명을 아주 간략히 하겠습니다.
평면 상에 수평 선분이 n(<=5000)개 주어집니다.
주어진 모든 선분을 지나는 직선을 그을 수 있냐는 게 문제입니다.
가능하면 YES, 불가능하면 NO를 출력하면 됩니다.
[spoiler="더 보기..."] 뉴스에 대회 현장 중계 글을 읽어보시면 JM님의 댓글 중에 해답이 있습니다.
우선 답이 YES라고 가정하고, 가능한 직선 중 하나를 구했다고 해보죠.
그 직선이 어떤 선분의 왼쪽 꼭지점을 지나지 않는다면, 직선을 왼쪽으로 약간 평행이동 시킬 수 있습니다.
그렇게 최대한 왼쪽으로 평행이동 시키면 언젠가 어떤 선분의 왼쪽 꼭지점과 만나겠죠.
그러므로 답이 YES라면, 어떤 선분의 왼쪽 꼭지점을 지나는 답이 항상 존재합니다.
이것을 떠올리셨다면 문제는 아주 쉽게 풀리는데요.
모든 왼쪽 꼭지점에 대해, 그 점에서 모든 선분을 지나는 직선을 그을 수 있는지 검사하면 됩니다.
여러가지 방법이 있겠지만, 저는 기울기를 이용해서 했습니다.
그림을 90도로 회전해서 보면, x와 y가 뒤바뀔 겁니다.
그러면 한 점에서 한 선분으로 그을 수 있는 직선의 기울기를 생각해보죠.
선분의 제일 아래쪽 점으로 그은 직선의 기울기와, 선분의 제일 위쪽 점으로 그은 직선의 기울기 사이가
모두 가능한 직선의 기울기가 됩니다. 그렇게 한 선분 당 가능한 기울기의 구간이 하나씩 나오겠죠.
그 모든 구간이 교집합이 있다면 답은 YES가 됩니다.
모든 왼쪽 꼭지점을 고려하는 데에 O(n),
그때마다 남은 모든 선분에 대해 기울기 구간을 구하는데 O(n).
그래서 전체 시간복잡도는 O(n^2) 입니다.
간단한 문제인데 괜히 말을 길게 설명한 것 같네요.
코드가 무척 간단하니, 코드를 보고 이해하셔도 될 것 같아요.
채점을 정확히 보내본 코드가 아니라서 약간 걱정되긴 하는데,
틀린 부분이 있다면 알려주세요. 'ㅁ')/

#include <algorithm>
#include <iostream>
#include <cstdio>
#include <cmath>
using namespace std;
#define FOR(i,a,b) for( int i=(a); i<(b); ++i)
#define REP(i,n) for(int i=0; i<(n); ++i)
#define ERR 1e-9
struct ele {
    int x,y1,y2;
};
int n;
ele dt[5001];
int main()
{
    int tn;
    cin>>tn;
    while (tn--) {
        cin>>dt[0].y2;
        cin>>n;
        FOR(i,1,n+1) cin>>dt[i].x>>dt[i].y1>>dt[i].y2;
        double l,r;
        int yes;
        REP(i,n+1) {
            l=-1e100,r=1e100;
            yes=1;
            REP(j,n+1) if (i!=j) {
                double c1,c2;
                c1=(dt[i].y1-dt[j].y1)/(double)(dt[i].x-dt[j].x);
                c2=(dt[i].y1-dt[j].y2)/(double)(dt[i].x-dt[j].x);
                if (c1>c2) swap(c1,c2);
                l=max(l,c1);
                r=min(r,c2);
                if (l>r && fabs(l-r)>ERR) {
                    yes=0;
                    break;
                }
            }
            if (yes) break;
        }
        if (yes) cout<<"YES"<<endl;
        else cout<<"NO"<<endl;
    }
    return 0;
}

실제 대회 때, 유리수를 써야될 지 약간 고민 했습니다만,
2007년 대회에서의 경험 상, 유리수를 안 써도 시도한 모든 문제에서 Yes가 나왔기 때문에
그냥 double을 썼습니다.
[/spoiler]