天下一プログラマーコンテスト2014予選A D問題 EMLauncher

幾何系の問題。線分がいっぱいあってそれを原点から半直線で全て貫くときの最小の貫く回数を求める。
端点だけ考えればいいというのはこういう問題の常套手段。
角度でソートしてあげてあとはなるべくたくさん貫くように貪欲に。
ただ、貫きをはじめる場所によって答えが変わるので全部試さなくてはいけなくて、O(N^2)

    int N; cin >> N;
    pair<double, int> kakudo[N*2];
    for(int i=0; i<N; i++){
        double x1, y1, x2, y2;
        cin >> x1 >> y1 >> x2 >> y2;
        double d1 =atan2(y1, x1);
        double d2 =atan2(y2, x2);
        if(d1 < 0) d1 += 2.0*M_PI;
        if(d2 < 0) d2 += 2.0*M_PI;
        if(d1 > d2) swap(d1, d2);
        if(d2-d1 > M_PI) swap(d1, d2);
        kakudo[i] = make_pair(d1, i);
        kakudo[i+N] = make_pair(d2, i+N);
    }
    sort(kakudo, kakudo+N*2);
    int mini = 1e9;
    for(int i=0; i<N*2; i++){
        int res = 0;
        int now = 0;
        int j = i;
        int in[2000] = {};
        do{
            if(kakudo[j].second < N) in[kakudo[j].second] = now;
            if(kakudo[j].second >= N && in[kakudo[j].second-N] == now){
                res++;now++;
            }
            j++;
            if(j == 2*N) j = 0;
        }while(j!=i);
        mini = min(mini, res);
    }
    cout << mini << endl;