http://agc019.contest.atcoder.jp/tasks/agc019_c
前提知識
解法
http://agc019.contest.atcoder.jp/submissions/1548182
まず、スタートが左下、ゴールがそれに対して右上となるように座標を変換する。
これは
- X1 > X2であれば全てのX座標を10^8 - Xとする
- Y1 > Y2であれば全てのY座標を10^8 - Yとする
ことで変換できる。
経路が最小となるパターンは、スタートからゴールまでなるべく多くの○を通るパターンである。
スタートとゴールへの最短経路のうち○が最も多くなる時の個数を計算するが、これはLISとなっていることが分かる。
これは○をX座標昇順で並べた時に、そのY座標の配列に対するLISが求めたい個数と一致している。
そのため、X座標昇順ソートして、Y座標に対してLISを取る。
1つ○を経由するごとに「20-5π」だけ経路を減らせるため、-LIS(20-5π)をすれば答え。
コーナーケースとして最後のサンプルのように円を直線に横切らないといけないパターンがあるが、
これはLIS=min(X2-X1,Y2-Y1)+1のときだけである。
これを満たさないということは空いたスペースがあるということで、ここで直進とならないパターンに変更できるためである。
直線に横切るため、追加で+5πをして答え
double PI = 2 * acos(0.0); typedef long long ll; string A; int X1, Y1, X2, Y2, N, X[201010], Y[201010]; //--------------------------------------------------------------------------------------------------- void _main() { cin >> X1 >> Y1 >> X2 >> Y2 >> N; rep(i, 0, N) cin >> X[i] >> Y[i]; if (X1 > X2) { X1 = 100000000 - X1; X2 = 100000000 - X2; rep(i, 0, N) X[i] = 100000000 - X[i]; } if (Y1 > Y2) { Y1 = 100000000 - Y1; Y2 = 100000000 - Y2; rep(i, 0, N) Y[i] = 100000000 - Y[i]; } vector<pair<int, int>> v; rep(i, 0, N) if (Y1 <= Y[i] && Y[i] <= Y2 && X1 <= X[i] && X[i] <= X2) v.push_back({ X[i], Y[i] }); sort(v.begin(), v.end()); vector<int> vv; vv.push_back(-1); fore(p, v) vv.push_back(p.second); vv.push_back(INT_MAX / 2 - 1); LIS lis(vv); double ans = 100.0 * (X2 - X1 + Y2 - Y1); ans += (5.0 * PI - 20.0) * lis.lis; if (lis.lis == min(X2 - X1, Y2 - Y1) + 1) ans += 5.0 * PI; printf("%.15f\n", ans); }