//Sasayego! Sasayego! Shinzou wo Sasageyo!
#include <iostream>
#include <iomanip>
#include <algorithm>
#include <cmath>
#include <ctime>
#include <cstring>
#include <vector>
#include <set>
#include <map>
#include <stack>
#include <queue>
#include <deque>
#include <numeric>
#include <bitset>
#include <ctime>
#define debug(x) cerr << #x << " = " << x << endl
#define lid (id << 1)
#define rid (lid ^ 1)
using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair <ll, ll> pll;
typedef pair <int, int> pii;
typedef pair <ll, pii> edge;
const int maxN = 2e3 + 5;
const ll INF = 1e18;
const ll MOD = 1e9 + 7;
int arumin[4][4], m, par[maxN];
int X[maxN], Y[maxN], rad[maxN];
edge E[maxN * maxN];
ll SQ(ll x){
ll lt = 0, rt = MOD;
while (rt - lt > 1){
ll md = (lt + rt) >> 1;
(md * md > x ? rt : lt) = md;
}
return rt;
}
ll dist(int a, int b){
ll x = X[a] - X[b];
ll y = Y[a] - Y[b];
return SQ(x * x + y * y);
}
int getpar(int v){
return (par[v] == v ? v : par[v] = getpar(par[v]));
}
void join(int u, int v){
u = getpar(u);
v = getpar(v);
par[u] = v;
return;
}
void put(int a, int b, int x){
arumin[a][b] = min(arumin[a][b], x);
arumin[b][a] = min(arumin[b][a], x);
return;
}
int main(){
time_t START = clock();
ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
iota(par, par + maxN, 0);
int n, q; scanf("%d%d", &n, &q);
int w, h; scanf("%d%d", &w, &h);
E[m++] = {w, {0, 2}};
E[m++] = {h, {1, 3}};
for (int i = 4; i < n + 4; i++){
scanf("%d%d%d", X + i, Y + i, rad + i);
E[m++] = {X[i] - rad[i], {0, i}};
E[m++] = {Y[i] - rad[i], {1, i}};
E[m++] = {w - X[i] - rad[i], {2, i}};
E[m++] = {h - Y[i] - rad[i], {3, i}};
for (int j = 4; j < i; j++)
E[m++] = {dist(j, i) - rad[i] - rad[j], {j, i}};
}
sort(E, E + m);
for (int i = 0; i < 4; i++)
for (int j = 0; j < 4; j++)
arumin[i][j] = MOD;
for (int x = 0; x < m; x++){
int d, a, b; pii pp;
tie(d, pp) = E[x];
tie(a, b) = pp;
join(a, b);
for (int i = 0; i < 4; i++)
for (int j = i + 1; j < 4; j++)
if (getpar(i) == getpar(j)){
if ((4 + i - j) & 1){
for (int k = 0; k < 4; k++)
if (i != k)
put(i, k, d);
}
else{
for (int k = 0; k < 2; k++)
for (int l = 0; l < 2; l++)
put((i + k) & 3, (j + l) & 3, d);
}
}
}
while (q--){
int r, p; scanf("%d%d", &r, &p);
p--; r <<= 1;
for (int i = 0; i < 4; i++)
if (r < arumin[p][i])
printf("%d", i + 1);
printf("\n");
}
time_t FINISH = clock();
cerr << "Execution time: " << (ld)(FINISH - START) / CLOCKS_PER_SEC * 1000.0 << " milliseconds.\n";
return 0;
}
Compilation message
park.cpp: In function 'int main()':
park.cpp:72:17: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
int n, q; scanf("%d%d", &n, &q);
~~~~~^~~~~~~~~~~~~~~~
park.cpp:73:17: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
int w, h; scanf("%d%d", &w, &h);
~~~~~^~~~~~~~~~~~~~~~
park.cpp:77:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d%d%d", X + i, Y + i, rad + i);
~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
park.cpp:110:18: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
int r, p; scanf("%d%d", &r, &p);
~~~~~^~~~~~~~~~~~~~~~
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
631 ms |
31840 KB |
Output is correct |
| 2 |
Incorrect |
624 ms |
32120 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
66 ms |
2168 KB |
Output is correct |
| 2 |
Incorrect |
61 ms |
2040 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
631 ms |
31840 KB |
Output is correct |
| 2 |
Incorrect |
624 ms |
32120 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
