ACM-ICPC World Finals 2016 J解法

J: Spin Doctor

問題

n人の個人情報が与えられる。i番目の人の情報は

• a_i : 覚えている円周率の桁数 0 ~ 2000000
• b_i : 髪の毛の本数 0 ~ 2000000
• c_i : 候補者Xに投票したかどうか 0/1

実数のパラメータS, Tを適切に決めて人々を (a_i * S + b_i * T) の値でソートし、その順番で c_i == 1の人がなるべく集まるようにしなさい。
より集まっている状態とは、ソートの順番でc_i == 1の最初の人と最後の人の近いということである。
その時の最初の人と最後の人の間に何人並んでいるか、最小値を求めよ。
ただし、(a_i * S + b_i * T)が同じ値になる場合は答えが大きくなるように並ぶとする。

制約

n <= 250000

解法

a, bで2次元平面にプロットすることを思いつくと、a_i * S + b_i * T は適当な直線への正射影(垂線の足)であることが分かる。
つまり、あらゆる角度の線に対して、その射影でc_i == 1 が偏る物を見つける問題である。
あらゆる角度の平行な2本の直線でc_i == 1を挟むと、その2線の間にある頂点が答えに成ることが見て取れる。
この2線を180度半周させるとc_i == 1の凸包が見えてくる。
つまり

c_i == 1: 常に凸包の内点(頂点、辺上を含む)、答えに加算

c_i == 0 かつ凸包の内点: 答えに加算

c_i == 0 かつ凸包の外点: 2本の直線がどこかの角度の時に加算

3つ目の項目で、角度は凸包への2本の接線から、その区間が分かる。
あとは問Gと同じ。
実数なのでタイブレークはEPSで厳しくずらしたケースを考えればよい。

コード

#include<cassert>
#include<complex>
#include<cstdio>
#include<iostream>
#include<vector>
#include<algorithm>
#include<string>
#include<cstring>
using namespace std;

typedef long long LL;
typedef vector<int> VI;

#define REP(i,n) for(int i=0, i##_len=(n); i<i##_len; ++i)
#define EACH(i,c) for(__typeof((c).begin()) i=(c).begin(),i##_end=(c).end();i!=i##_end;++i)
#define eprintf(s...)  fprintf(stderr, s)

template<class T> inline void amin(T &x, const T &y) { if (y<x) x=y; }
template<class T> inline void amax(T &x, const T &y) { if (x<y) x=y; }

typedef long double Double;
const Double EPS = 1e-8; // 0 ~~ [-EPS, EPS]
// const LL EPS = 0;
const Double INF = 1e12;
const Double PI = acos((Double)-1);

typedef complex<Double> Point;
const Point I(0, 1);

// abs(P a) ::= sqrt(a.x^2 + a.y^2);
// norm(P a) ::= a.x^2 + a.y^2;
// Point polar(rho, theta=0)

int sign(Double x) {
    if (x < -EPS) return -1;
    if (EPS < x) return 1;
    return 0;
}

namespace std {
    bool operator<(const Point &x, const Point &y) {
	return real(x) != real(y)? real(x) < real(y): imag(x) < imag(y);
    }
}

Double cross(const Point &x, const Point &y) {
    return imag(conj(x)*y);
}
Double dot(const Point &x, const Point &y) {
    return real(conj(x)*y);
}
Point normal(const Point &a) { return a / abs(a); }

struct Line : public vector<Point> {
    Line(const Point &a, const Point &b) {
	push_back(a); push_back(b);
    }
    Point vector() const {
	return back() - front();
    }
};

typedef vector<Point> Polygon;
Double area2(const vector<Point> &g) {
    Double r = 0;
    for (int i=0; i<(int)g.size(); i++)
	r += cross(g[i], g[(i+1)%g.size()]);
    return abs(r);
}

int ccw(Point a, Point b, Point c) {
    b-=a; c-=a;
    if (cross(b, c) > EPS) return 1; // counter clockwise
    if (cross(b, c) < -EPS) return -1; // clockwise
    if (dot(b, c) < -EPS) return 2; // c--a--b on line
    if (norm(b) < norm(c)) return -2; // a--b--c on line
    return 0;
}

Polygon convex_hull(vector<Point> ps, int *c=NULL) {
    int n = ps.size(), k = 0;
    sort(ps.begin(), ps.end());
    vector<Point> ch(2*n);
    for (int i=0; i<n; ch[k++] = ps[i++]) // lower -hull
	while (k >= 2 && ccw(ch[k-2], ch[k-1], ps[i]) != 1) --k;
    if (c) *c = k-1;
    for (int i = n-2, t = k+1; i >= 0; ch[k++] = ps[i--]) // upper -hull
	while (k >= t && ccw(ch[k-2], ch[k-1], ps[i]) != 1) --k;
    ch.resize(k-1);
    return ch;
}

int N;
Polygon T, F;

int main() {
    scanf("%d", &N);
    REP (i, N) {
	int x, y, c;
	scanf("%d%d%d", &x, &y, &c);
	Point p(x, y);
	p *= polar(1.0, 1.0);
	if (c) T.push_back(p);
	else F.push_back(p);
    }

    N = T.size();
    if (N == 1) {
	puts("1");
	return 0;
    }

    int inner = 0;

    int R;
    T = convex_hull(T, &R);
    {
	// outer points
	Polygon v;
	EACH (e, F) {
	    if (T[0].real() <= e->real() && e->real() <= T[R].real()) {
		// lower
		int lo, hi;
		lo = 0, hi = R;
		while (hi - lo > 1) {
		    int m = (lo + hi) / 2;
		    if (T[m].real() <= e->real()) lo = m;
		    else hi = m;
		}
		if (ccw(T[lo], T[lo+1], *e) == -1) {
		    v.push_back(*e);
		    continue;
		}

		lo = R, hi = T.size();
		while (hi - lo > 1) {
		    int m = (lo + hi) / 2;
		    if (T[m].real() >= e->real()) lo = m;
		    else hi = m;
		}
		if (ccw(T[lo], T[(lo+1)%T.size()], *e) == -1) {
		    v.push_back(*e);
		    continue;
		}
		inner++;
	    } else {
		v.push_back(*e);
	    }
	}
	F = v;
    }


    eprintf("%d %d %d\n", (int)T.size(), (int)F.size(), inner);
    int ans = N + inner + F.size();
    {
	// angle

	vector<pair<Double, int> > G;
	EACH (e, F) {
	    const Point &p = *e;

	    int k = rand();
	    for (int D=1<<21; D; D>>=1) {
		if (D > 1 && D * 2 > (int)T.size()) continue;
		int b = (k - 3 * D + (int)T.size() * 10) % T.size();
		k = b;
		assert(b >= 0);
		REP ($, 6) {
		    if (ccw(p, T[b], T[(b+D)%T.size()]) != 1 && ccw(p, T[(b+D)%T.size()], T[(b+D+D)%T.size()]) != -1) k = (b+D) % T.size();
		    b = (b + D) % T.size();
		}
	    }
	    Double A = arg(T[k%T.size()] - p);

	    k = rand();
	    for (int D=1<<21; D; D>>=1) {
		if (D > 1 && D * 2 > (int)T.size()) continue;
		int b = (k - 3 * D + (int)T.size() * 10) % T.size();
		k = b;
		assert(b >= 0);
		REP ($, 6) {
		    if (ccw(p, T[b], T[(b+D)%T.size()]) != -1 && ccw(p, T[(b+D)%T.size()], T[(b+D+D)%T.size()]) != 1) k = (b+D) % T.size();
		    b = (b + D) % T.size();
		}
	    }
	    Double B = arg(T[k%T.size()] - p);

	    while (B + EPS < A) B += 2 * PI;

	    assert(A <= B + EPS);
	    assert(B <= A + PI + EPS);

	    A -= EPS;
	    B += EPS;
	    G.push_back(make_pair(B, +1));
	    G.push_back(make_pair(A+PI, -1));
	}


	int len = G.size();
	REP (r, len) {
	    pair<Double, int> p = G[r];
	    G.push_back(make_pair(p.first + 1 * PI, p.second));
	    G.push_back(make_pair(p.first + 2 * PI, p.second));
	    G.push_back(make_pair(p.first + 3 * PI, p.second));
	}

	sort(G.begin(), G.end());

	int cur = 0;
	EACH (e, G) {
	    cur += e->second;
	    assert(cur >= 0);
	    amin(ans, N + inner + (int)F.size() - cur);
	}
    }

    printf("%d\n", ans);

    return 0;
}

日記

自分にも解けるマシな幾何。 Gと解法が被ってるのは残念。
凸包が見えると解法も自然と分かる。
図とか書きたかったけどそんな難しいわけでもないしいいか。
凸包への接線求めるの難しかったけど、二分探索で良かったか。