日記 (2018 年 2 月 24 日)
AGC021 に出てきました。 結果は、 1 問正解 300 点で 1032 人中 469 位でした。 レートは 869 (緑) まで上がりました。 早く青くなりたい。
さて、 今回は AGC021 の B 問題についてまとめておきます。 問題はこちらです。
平面上の
ということで、 問題となるのはボロノイ領域が十分遠方まで広がる点というのはどういう点かということですが、 少し考えれば、 与えられた
凸包を求めるアルゴリズムはいくつかあるようですが、 今回は 「ギフト包装法」 と呼ばれるアルゴリズムを使ってみます。
凸包を成す頂点が、 その凸方を 1 周する順番に求まります。
処理する点の数を
このアルゴリズムでは、 以下のように凸包を求めます。
まず、 絶対に凸包の頂点となるような点
上の点
実際のプログラムは以下のような感じです。
public void run() {
BetterScanner scanner = new BetterScanner(System.in);
int n = scanner.nextInt();
int[] xx = new int[n];
int[] yy = new int[n];
// 最も上 (y 座標が小さい) にある点のインデックスを求める
// y 座標が最小の点が複数ある場合はその中の最も左のものにしておく
int a = 0;
int minY = 10000000;
int minX = 10000000;
for (int i = 0 ; i < n ; i ++) {
int x = scanner.nextInt();
int y = scanner.nextInt();
xx[i] = x;
yy[i] = y;
if (y < minY || (y == minY && x < minX)) {
minY = y;
minX = x;
a = i;
}
}
List<Integer> outers = new ArrayList(n);
int b;
do {
outers.add(a);
b = 0;
for (int c = 1 ; c < n ; c ++) {
if (b == a) {
b = c;
} else {
// 2 ベクトル AB, AC の外積を計算
// これが正なら直線 AB に対して点 C は左側
long v = (long)(xx[a] - xx[b]) * (yy[a] - yy[c]) - (long)(xx[a] - xx[c]) * (yy[a] - yy[b]);
long ab = (long)(xx[a] - xx[b]) * (xx[a] - xx[b]) + (long)(yy[a] - yy[b]) * (yy[a] - yy[b]);
long ac = (long)(xx[a] - xx[c]) * (xx[a] - xx[c]) + (long)(yy[a] - yy[c]) * (yy[a] - yy[c]);
// 直線 AB 上に点 C がある (外積が 0) 場合は点 C の方が遠いときに更新
if (v > 0L || (v == 0L && ac > ab)) {
b = c;
}
}
}
a = b;
// 1 周するまで繰り返し
} while (a != outers.get(0));
int m = outers.size();
double[] probs = new double[n];
for (int k = 0 ; k < m ; k ++) {
int i = outers.get(k);
int nextI = (k < m - 1) ? outers.get(k + 1) : outers.get(0);
int previousI = (k >= 1) ? outers.get(k - 1) : outers.get(m - 1);
// 凸包上で隣り合う点との垂直二等分線の角度を計算
double nextTan = Math.atan2(yy[nextI] - yy[i], xx[nextI] - xx[i]) + Math.PI / 2;
double previousTan = Math.atan2(yy[i] - yy[previousI], xx[i] - xx[previousI]) + Math.PI / 2;
if (nextTan > Math.PI) {
nextTan -= 2 * Math.PI;
}
if (previousTan > Math.PI) {
previousTan -= 2 * Math.PI;
}
double range = previousTan - nextTan;
if (range < 0) {
range += 2 * Math.PI;
}
// 隣り合う点との垂直二等分線の角度の差を 2π でわったものが確率
probs[i] = range / (2 * Math.PI);
}
for (int i = 0 ; i < n ; i ++) {
System.out.println(probs[i]);
}
}
ちなみに本番では、 最も上にある点のインデックスを求める処理を間違えて書いていて、 みすみす 600 点を逃しました。 つらいです。