ACM-ICPC World Finals 2016 G解法

G: Oil

問題

地面水平方向x軸。垂直方向下向y軸。y=0が地表の2次元座標上の問題。
油井は地中にあり、地表と水平な線分で表される。
n個の油井のいち情報が与えられる。
地表から1本の直線状に任意の角度でドリルで掘って、接するか交差した油井の油を得ることができる。
油井の量はその長さに比例する。

ドリルで掘る位置・角度を適切に求め油量の最大値を出力せよ。
題意は図を見れば一発なので。

制約

1 <= n <= 2000

解法

ドリルの直線は平行移動させてどこかの油井の端点を通る直線にずらすことができる。
回転も考えると2点決めて、そのドリルの直線に交差する油井を数えればよいがO(n^3)でTLE（15secで通るかもしれないけど）。

1点決めて、そこを通るドリルの直線を回転させると、油井にかかったら油量が増加し油井から離れたら減少する。
この油井の端点をイベントとすると、選んだ1点から見た角度でイベントが発生する、角度に対する平面走査法で解くことができる。

固定する点は2n個、残りの2(n-1)個の端点がイベントになり、ソーティングにO(n log n)。全体でO(n^2 log n)。

コード

#include<cmath>
#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; }

int N;
int X0[2011], X1[2011], Y[2011];
LL ans;

const double EPS = 1e-8;

void calc(double x, double y, LL cur) {
    amax(ans, cur);
    vector<pair<double, int> > v;
    REP (i, N) {
	int d = X1[i] - X0[i];
	if (y < Y[i]) {
	    v.push_back(make_pair(atan2(Y[i] - y, X0[i] - x - EPS), -d));
	    v.push_back(make_pair(atan2(Y[i] - y, X1[i] - x + EPS), +d));
	} else if (y > Y[i]) {
	    v.push_back(make_pair(atan2(y - Y[i], x - X0[i] + EPS), +d));
	    v.push_back(make_pair(atan2(y - Y[i], x - X1[i] - EPS), -d));
	}
    }

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

    EACH (e, v) {
	cur += e->second;
	amax(ans, cur);
    }
}

int main() {
    scanf("%d", &N);
    REP (i, N) {
	scanf("%d%d%d", X0+i, X1+i, Y+i);
	if (X0[i] > X1[i]) swap(X0[i], X1[i]);
    }

    REP (i, N) {
	calc(X0[i], Y[i], X1[i] - X0[i]);
	calc(X1[i], Y[i], X1[i] - X0[i]);
    }

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

    return 0;
}

日記

どこでも見る頻出問題。しかし基礎的で教育的な良問だと思う。