C - Fountain Walk
概要
x 軸方向と y 軸方向にそれぞれ $10^8$ 本の道が $100m$ 間隔で直交するように通っている(要は $100m$ 間隔のだだっ広いグリッドがある)。
この道の交差点上に $N$ 個の噴水がそれぞれ $(X_i, Y_i)$ に置かれている。噴水は半径 $10m$ の円形をしていて、その外周に道が通っている。また 1 つの道上に 2 つ以上の噴水が置かれていることはない 。
このとき、 $(x_1, y_1)$ から $(x_2, y_2)$ へ移動するための最短距離を求めよ。
制約
- $0 \leq x_1, y_1, x_2, y_2, X_i, Y_i \lt 10^8$
- $1 \leq N \leq 2 \times 10^5$
- $i \neq j$ のとき、 $X_i \neq X_j$ かつ $Y_i \neq Y_j$
- スタートとゴールに噴水は置かれていない
解説
適当に上下左右判定することで、 $x_1 \leq x_2$ かつ $y_1 \leq y_2$ のケースに帰着できる。
最短経路ということで、まず x 正方向と y 正方向に移動することだけ考えればいい。
よって $(x_1, y_1)$ と $(x_2, y_2)$ を対頂角とする長方形に入っていない噴水は無視していい。
そういったルートの中で、できるだけ多く噴水で曲がるようなルートを探すことを考える。
1 つのルートで 2 つの噴水 $i, j$ で曲がることができる条件は、 $X_i < X_j$ かつ $Y_i < Y_j$ が成立することである。
つまり任意の 2 つがこれを満たす最大の噴水の集合を見つければいい。
そしてこれは、 $X_i$ について昇順にソートすれば、 $Y_i$ の 最長増加部分列 となる。
有名問題なので解き方は割愛。
最後に、この問題にはコーナーケースが存在する。それが「曲がる回数が長方形の幅と同じケース」である。
この場合、必ず 1 回は噴水を突っ切る必要があるため、その分のロスが生じる。
実装例
提出 #3179466 - AtCoder Grand Contest 019
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
|
#include <iostream>
#include <iomanip>
#include <algorithm>
#include <cmath>
#include <set>
#include <map>
#include <vector>
using namespace std;
template <typename T>
using V = vector<T>;
using ll = long long;
#define SIZE(v) (static_cast<ll>((v).size()))
#define ALL(v) (v).begin(), (v).end()
#define SORT(v) sort(ALL(v))
const double PI = acos(-1);
// BITオブジェクト、Range Maximum Queryバージョン
class BIT {
public:
explicit BIT(ll N, ll v) : V_NUM(N) {
data.resize(N);
fill(ALL(data), v);
}
ll query(ll i) {
ll ret = 0;
while (i > 0) {
ret = max(ret, data[i]);
i -= (i & -i);
}
return ret;
}
void update(ll i, ll v) {
while (i < V_NUM) {
data[i] = max(data[i], v);
i += (i & -i);
}
}
ll V_NUM;
V<ll> data;
};
// 座標(coordinate)を保持する構造体
struct coo {
coo(ll _x = 0, ll _y = 0) : x(_x), y(_y){};
ll x;
ll y;
// ソートするために比較演算子をオーバーロードする
bool operator<(const coo& r) const {
return x == r.x ? y < r.y : x < r.x;
}
};
// Y座標で座圧をする
map<ll, ll> compress(const V<coo>& a) {
set<ll> sety;
for (coo c : a) {
sety.insert(c.y);
}
map<ll, ll> ret;
ll idx = 1;
for (ll y : sety) {
ret[y] = idx;
++idx;
}
return ret;
}
int main() {
cout << fixed << setprecision(12);
// startとgoal
coo s, g;
cin >> s.x >> s.y >> g.x >> g.y;
// startの方が下にくるようにする
if (s.y > g.y) swap(s, g);
ll N;
cin >> N;
V<coo> a;
// 長方形領域内にある噴水のみを記録する
for (ll i = 0; i < N; ++i) {
ll x, y;
cin >> x >> y;
if (y < s.y || g.y < y) continue;
if (s.x < g.x) {
if (s.x <= x && x <= g.x) {
a.push_back(coo(x - s.x, y - s.y));
}
} else {
// startとgoalのX座標が逆の場合はこっちも左右反転する
if (g.x <= x && x <= s.x) {
a.push_back(coo(s.x - x, y - g.y));
}
}
}
SORT(a);
map<ll, ll> com = compress(a);
BIT bit(SIZE(com) + 1, 0);
for (coo c : a) {
ll y = com[c.y];
bit.update(y, bit.query(y) + 1);
// bit.query(y)でy以下の最大値を求める
// それに1加えた値で更新
}
// BIT全体の最大値が答え
ll turn = bit.query(SIZE(com));
double ans = (abs(g.x - s.x) + abs(g.y - s.y)) * 100;
// 噴水を無視した場合の距離
ans -= (20 - PI * 5) * turn;
// 曲がる分だけ削れる
// コーナーケース
if (turn == abs(g.y - s.y) + 1 || turn == abs(g.x - s.x) + 1) ans += PI * 5;
cout << ans << endl;
return 0;
}
|