| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 1219696 | DeathIsAwe | Park (BOI16_park) | C++20 | 0 ms | 0 KiB |
=#include <bits/stdc++.h>
using namespace std;
#define mp make_pair
#define ff first
#define ss second
#define ll long long
#define float double
#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")
float adjmatrix[2010][2010];
const float maxn = 10000000000000;
float connection(int a, int b) {
vector<float> dist(2010, maxn);
priority_queue<pair<float, int>, vector<pair<float, int>>, greater<pair<float, int>>> pq;
pq.push(mp((float)0, a));
pair<float, int> node;
while (pq.size() > 0) {
node = pq.top(); pq.pop();
if (dist[node.ss] != maxn) continue;
dist[node.ss] = node.ff;
for (int i=0;i<2010;i++) {
if (dist[i] != maxn || adjmatrix[node.ss][i] == -1) continue;
pq.push(mp(max(adjmatrix[node.ss][i], dist[node.ss]), i));
}
}
return dist[b];
}
bool check(int a, int b, vector<float> wall, int r) {
if (a == b) return true;
if (wall[a] >= 2*r && wall[b] >= 2*r) {
if (abs(a - b) == 2) {
if (wall[5] >= 2*r && wall[6] >= 2*r) return true;
} else {
if (a/3 == b/3) {
if (wall[5] >= 2*r) return true;
} else {
if (wall[6] >= 2*r) return true;
}
}
}
return false;
}
int main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL);
for (int i=0;i<2010;i++) {
for (int j=0;j<2010;j++) {
adjmatrix[i][j] = -1;
}
}
int n, m, w, h; cin >> n >> m >> w >> h;
vector<vector<int>> trees(n, vector<int>(3));
vector<pair<int,int>> visitors(m);
for (int i=0;i<n;i++) {
cin >> trees[i][0] >> trees[i][1] >> trees[i][2];
}
for (int i=0;i<m;i++) {
cin >> visitors[i].ff >> visitors[i].ss;
}
for (int i=0;i<n;i++) {
for (int j=0;j<n;j++) {
if (i == j) continue;
adjmatrix[i][j] = sqrt(pow(trees[i][0] - trees[j][0], 2) + pow(trees[i][1] - trees[j][1], 2)) - trees[i][2] - trees[j][2];
}
}
for (int i=0;i<n;i++) {
adjmatrix[i][n] = h - trees[i][1] - trees[i][2];
adjmatrix[i][n + 1] = w - trees[i][0] - trees[i][2];
adjmatrix[i][n + 2] = trees[i][1] - trees[i][2];
adjmatrix[i][n + 3] = trees[i][0] - trees[i][2];
adjmatrix[n][i] = adjmatrix[i][n];
adjmatrix[n + 1][i] = adjmatrix[i][n + 1];
adjmatrix[n + 2][i] = adjmatrix[i][n + 2];
adjmatrix[n + 3][i] = adjmatrix[i][n + 3];
}
//for (int i=0;i<5;i++) {
// for (int j=0;j<5;j++) {
// cout << adjmatrix[i][j] << ' ';
// }
// cout << '\n';
//}
vector<float> wall(7);
float ne, es, sw, wn, ns, we;
ne = connection(n, n + 1); es = connection(n + 1, n + 2); sw = connection(n + 2, n + 3); wn = connection(n + 3, n);
ns = connection(n, n + 2); we = connection(n + 1, n + 3);
wall[1] = sw; wall[2] = es; wall[3] = ne; wall[4] = wn; wall[5] = ns; wall[6] = we;
//for (int i=1;i<7;i++) {
// cout << wall[i] << ' ';
//} cout << '\n';
for (int i=0;i<m;i++) {
for (int j=1;j<5;j++) {
if (check(visitors[i].ss, j, wall, visitors[i].ff)) cout << j;
}
cout << '\n';
}
}