Codeforces #299 Div1 C. Tavas and Pashmaks

凸包デビュー。

問題

Problem - E - Codeforces

解法

(1/s, 1/r)の点を2次元上にプロットしていき,その凸包を考える。この時,凸法の下側にあるのが答え。

理由がはっきりわからないんですが,こんな感じだと思います。
前提としては,水泳とランニングにかかる時間の合計が

というように内積で表せることを利用します。

示すべきこととしては,「内積が最小になるとしたら,凸法の下半分の部分にしかないということ」および「凸包の下側には必ず1位になるような(S, R)の組が存在する」ということです。

まず「凸包の下側には必ず1位になるような(S, R)の組が存在する」ということから。

図で,「注目する点」(Pとする)と書かれている点に,内積を最小とするようなベクトル(S, R)が存在することを示したいです。

まず一番上側にある点(Aとする)と比べてみましょう。あるベクトルv=(S, R)について,v*Pという内積とv*Aという内積が等しくなるような直線は,赤色の線で表されます(赤色の点線はそれに直行する直線であり,これはAとPを結ぶ直線として表すことができる)。

よって,Aよりもvとの内積を小さくするには赤色の線よりもy軸側に直線を持ってくれば良いです。

次に,Pの右隣にある点(Bとする)と比べます。同様に,緑の直線よりもx軸側にあれば良いです。
更に右隣にある点(Cとする)と比べると,青の直線よりもx軸側にあれば良いです。

この様子を見ていると気づきますが,要するに調べるべき点はPの両隣にある点のみですね(青の直線は必ず緑の直線よりも外側に来るので調べる必要はない)。また,図形は凸なので赤直線で表される範囲と緑直線で表される範囲が存在しないこともなさそうです(これ証明はよくわからないので多分ですが)。

ということで凸包の下側には必ず1位になるような(S, R)の組が存在することがわかりました。

次に「内積が最小になるとしたら,凸法の下半分の部分にしかないということ」です。

さっきと似ているので察してください。多分すべての点が凸法の中にあるので必ずある辺と交わり,その辺を構成する2点と内積比べをすると取り得ない方向ベクトルしか(S, R)として選択出来ない,的な感じになるんでしょうかね？よくわかりません。

追記
上みたいに難しく考えなくても全然良かったですね。。。

@mayoko_ 「傾き -R/S の直線を左下の方からだんだん右上に近づけていって, 最初に通る点が最適」というのを考えればすぐ出そう.

— みさわ (@Mi_Sawa) 2015, 6月 16

内積になることを考えると,要するに
を最小にするの組み合わせを点群の中から求める問題に帰着します。
大学受験のノリで

とすると

となり,これの意味するところは
「直線のaをどんどん大きくしていった時,初めて点群とぶつかるような点はどこになるでしょう?」
ということです。これは確かに凸法の下側みれば分かりそうな気がします。

double eps = 1e-22;

double add(double a, double b) {
    if (abs(a+b) < eps * (abs(a)+abs(b))) return 0;
    return a+b;
}

bool equal(double a, double b) {
    return add(a, -b) == 0;
}

struct P {
    double x, y;
    P() {}
    P(double x, double y) : x(x), y(y) {}
    P operator+(P p) const {return P(add(x, p.x), add(y, p.y));}
    P operator-(P p) const {return P(add(x, -p.x), add(y, -p.y));}
    P operator*(double d) const {return P(x*d, y*d);}
    double dot(P p) const {return add(x*p.x, y*p.y);} // 内積
    double det(P p) const {return add(x*p.y, -y*p.x);} // 外積
    double dist(P p) const {return (x-p.x)*(x-p.x) + (y-p.y)*(y-p.y);} // 距離
    bool operator<(const P& rhs) const {
        if (x != rhs.x) return x < rhs.x;
        return y < rhs.y;
    }
    bool operator==(const P& rhs) const {
        return equal(x, rhs.x) && equal(y, rhs.y);
    }
};

// 線分p1-p2上に点qがあるかを判定する
bool on_seg(P p1, P p2, P q) {
    return (p1-q).det(p2-q) == 0 && (p1-q).dot(p2-q) <= 0;
}

// 直線p1-p2と直線q1-q2の交点
P intersection(P p1, P p2, P q1, P q2) {
    return p1+(p2-p1)*((q2-q1).det(q1-p1)/(q2-q1).det(p2-p1));
}

// 凸包
vector<P> convex_hull(vector<P> ps) {
    int n = ps.size();
    sort(ps.begin(), ps.end());
    int k = 0;         // 凸包の頂点数
    vector<P> qs(n*2); // 構築中の凸包
    // 下側凸包の作成
    for (int i = 0; i < n; i++) {
        while (k > 1 && (qs[k-1]-qs[k-2]).det(ps[i]-qs[k-1]) <= 0) k--;
        qs[k++] = ps[i];
    }
    qs.resize(k);
    return qs;
    // 上側凸包の作成
    for (int i = n-2, t = k; i >= 0; i--) {
        while (k > t && (qs[k-1]-qs[k-2]).det(ps[i]-qs[k-1]) <= 0) k--;
        qs[k++] = ps[i];
    }
    qs.resize(k-1);
    return qs;
}

int ma[11111];
int s[211111], r[211111];
vector<int> memo[11111];

int main() {
    cin.tie(0);
    ios::sync_with_stdio(false);
    int n;
    cin >> n;
    vector<P> ps(n);
    map<P, vi> m;
    for (int i = 0; i < n; i++) {
        cin >> s[i] >> r[i];
        ps[i] = P(1./s[i], 1./r[i]);
        m[ps[i]].push_back(i);
        ma[s[i]] = max(r[i], ma[s[i]]);
    }
    for (int i = 0; i < n; i++) {
        if (r[i] == ma[s[i]]) memo[s[i]].push_back(i+1);
    }
    if (n <= 2) {
        for (int i = 0; i < n; i++) {
            cout << i+1 << " ";
        }
        cout << endl;
        return 0;
    }
    auto qs = convex_hull(ps);
    sort(qs.begin(), qs.end());
    int y = -1;
    vector<int> ans;
    for (int i = 10000; i >= 1; i--) {
        if (memo[i].size() == 0) continue;
        if (y != -1 && ma[y] >= ma[i]) continue;
        P p = P(1./i, 1./ma[i]);
        //if (binary_search(qs.begin(), qs.end(), p)) {
        if (find(qs.begin(), qs.end(), p) != qs.end()) {
            for (int el : memo[i]) {
                ans.push_back(el);
            }
        }
        y = i;
    }
    sort(ans.begin(), ans.end());
    for (int el : ans) {
        cout << el << " ";
    }
    cout << endl;
    return 0;
}