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

問題ページ

原点からの半直線を引くので関係があるのは始点と終点の偏角である。各線分を[始点の偏角、終点の偏角]の区間に置き換えると、「ある区間の集合が与えられる。任意の区間についていずれかの要素を含むような偏角の集合のうち、最小の要素のものを答えろ。」という問題に置き換えられる。

偏角は循環しているが、一旦単純化して循環していない単なる区間の列について考える。終点でソートしておく。このとき、一番最初の区間については終点を集合に追加するべきである。また、始点が一番最初の区間の終点より前にある区間についても条件を満たす。条件をまだ満たしていない区間のうち、一番最初の区間について同様の処理を行う。

このような循環する座標系においては始点を固定することで列に置き換えるのが常套手段で、この問題では始点となる区間を $O(N)$ 個試すことで循環している条件に対応することができる。

線分を偏角の区間に置き換えるところについて、誤差の処理だったりが結構大変
$($ 偏角 $) \gt 0$ かつ $($ 始点の偏角 $) \lt ($ 終点の偏角 $)$ かつ $($ 終点の偏角 $) - ($ 始点の偏角 $) \lt \pi$ となるようにしておく。こうしても一般性を失わないし、頭が壊れにくくなる。 $($ 始点の偏角 $)$ から eps を引き、 $($ 終点の偏角 $)$ に eps を足しておくといいっぽい。

#include <bits/stdc++.h>  
using namespace std;  
using ll = long long;  
using PII = pair<ll, ll>;  
#define FOR(i, a, n) for (ll i = (ll)a; i < (ll)n; ++i)  
#define REP(i, n) FOR(i, 0, n)  
#define ALL(x) x.begin(), x.end()  
template<typename T> void chmin(T &a, const T &b) { a = min(a, b); }  
template<typename T> void chmax(T &a, const T &b) { a = max(a, b); }  
struct FastIO {FastIO() { cin.tie(0); ios::sync_with_stdio(0); }}fastiofastio;  
#ifdef DEBUG  
#include "../program_contest_library/memo/dump.hpp"  
#else  
#define dump(...)  
#endif  
const ll INF = 1LL<<60;  
  
using R = long double;  
const R EPS = 1e-8;  
const R PI = atan(1)*4;  
  
inline int sgn(const R &r) { return (r>EPS) - (r<-EPS); }  
inline int sgn(const R &r1, const R &r2) { return sgn(r1-r2); }  
  
int main(void) {  
    ll n;  
    cin >> n;  
    vector<ll> sx(n), sy(n), gx(n), gy(n);  
    REP(i, n) cin >> sx[i] >> sy[i] >> gx[i] >> gy[i];  
  
    vector<pair<R,R>> v0(n);  
    REP(i, n) {  
        R sarg = atan2l(sy[i], sx[i]);  
        R garg = atan2l(gy[i], gx[i]);  
        if(sarg > garg) swap(sarg, garg);  
        if(garg-sarg > PI) swap(sarg, garg);  
        sarg -= EPS;  
        garg += EPS;  
        if(sarg < 0) sarg += 2*PI;  
        while(garg < sarg) garg += 2*PI;  
        v0[i] = {sarg, garg};  
    }  
    sort(ALL(v0));  
  
    ll ans = n;  
    REP(i, n) {  
        // 区間iの終点に対応する半直線を引く  
        // この半直線に交差しない区間を列挙する  
        R t = v0[i].second;  
        vector<pair<R,R>> v;  
        REP(j, n) {  
            bool cross1 = sgn(v0[j].first, t) <= 0 && sgn(t, v0[j].second) <= 0;  
            bool cross2 = sgn(v0[j].first, t+2*PI) <= 0 && sgn(t+2*PI, v0[j].second) <= 0;  
            if(cross1 || cross2) continue;   
            if(sgn(t, v0[j].first) < 0) v.emplace_back(v0[j].first, v0[j].second);  
            if(sgn(v0[j].second, t) < 0) v.emplace_back(v0[j].first+2*PI, v0[j].second+2*PI);  
        }  
  
        // 終点でソートして貪欲にとっていく  
        sort(ALL(v), [](PII l, PII r){  
            return PII(l.second, l.first) < PII(r.second, r.first);  
        });  
        ll ret = 1, x = 0;  
        for(; x<(ll)v.size();) {  
            ll hold = x;  
            for(; x<(ll)v.size() && sgn(v[x].first, v[hold].second) <= 0; ++x);  
            ret++;  
        }  
        chmin(ans, ret);  
    }  
    cout << ans << endl;  
  
    return 0;  
}

ferinの競プロ帳

競プロについてのメモ

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