/**
SXR0aXAkI0JwbXptI3FhI3Z3I293bCNqY2IjUG0jMCNicG0jVHFkcXZvLyNCcG0jQW10bjBhY2phcWFicXZvLyNNYm16dml0MSNWdyNhdGN1am16I2tpdiNhbXF9bSNQcXUjVnd6I0F0bW14MSNQcWEjaXptI2l0dCNicHF2b2EjUXYjYnBtI3BtaWRtdmEjaXZsI3d2I21pemJwMSNFcHcjcWEjYnBtem0ja2l2I3F2Ym16a21sbSNRdiNQcWEjeHptYW12a20jbXtrbXhiI0lhI3BtI3htenVxYmJtYnBHI1BtI3N2d2VtYnAjRXBpYiMraXh4bWl6bWJwI2J3I1BxYSNrem1pYmN6bWEjSWEsI0ptbnd6bSN3eiNJbmJteiN3eiNKbXBxdmwjYnBtdTEjVnd6I2FwaXR0I2JwbXwja3d1eGlhYSNJY29wYiN3biNwcWEjc3Z3ZXRtbG9tI017a214YiNpYSNQbSNlcXR0bWJwMSNQcWEjYnB6d3ZtI2x3YnAjbXtibXZsI1dkbXojYnBtI3BtaWRtdmEjSXZsI3d2I21pemJwLyNpdmwjUG0jbm1tdG1icCNWdyNuaWJxb2NtI3F2I29jaXpscXZvI0l2bCN4em1hbXpkcXZvI2JwbXUvI053eiNQbSNxYSNicG0jVXdhYiNQcW9wMSNCcG0jQWN4em11bSMrcXYjb3R3enwsMQ==
*/
#include <cstring>
#include <vector>
#include <list>
#include <map>
#include <set>
#include <deque>
#include <stack>
#include <bitset>
#include <algorithm>
#include <functional>
#include <numeric>
#include <utility>
#include <sstream>
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <queue>
#include <cmath>
#include <cstdlib>
#include <ctime>
#include <cassert>
#define F first
#define S second
#define endl '\n'
#define deb(x) cout<<#x<<' '<<x<<endl;
#define pb push_back
#define int __int64_t
const long long MOD = 1e9 + 7;
const long long MAXN = 1e6 + 1;
using namespace std;
typedef long long ll;
long long readInt() {
bool minus1 = false;
long long result = 0;
char ch;
ch = getchar();
while (true) {
if (ch == '-') break;
if (ch >= '0' && ch <= '9') break;
ch = getchar();
}
if (ch == '-') minus1 = true; else result = ch-'0';
while (true) {
ch = getchar();
if (ch < '0' || ch > '9') break;
result = result*10 + (ch - '0');
}
if (minus1)
return -result;
else
return result;
}
const double eps = 1e-9;
bool equalTo ( double a, double b ){ if ( fabs ( a - b ) <= eps ) return true; else return false; }
bool notEqual ( double a, double b ){if ( fabs ( a - b ) > eps ) return true; else return false; }
bool lessThan ( double a, double b ){ if ( a + eps < b ) return true; else return false; }
bool lessThanEqual ( double a, double b ){if ( a < b + eps ) return true; else return false;}
bool greaterThan ( double a, double b ){if ( a > b + eps ) return true;else return false;}
bool greaterThanEqual ( double a, double b ){if ( a + eps > b ) return true;else return false;}
const int N = 2222;
struct edge{
int s, e, x;
};
vector<edge> v;
vector <int> g[N];
int ans[N][N];
int d[N][N];
int par[N];
int G[N][N];
struct Point {
double x, y, r;
};
Point a[N];
double dist(int i, int j) {
double X = (a[i].x - a[j].x);
double Y = (a[i].y - a[j].y);
return sqrt(X*X+Y*Y);
}
bool cmp(edge a, edge b) {
return a.x < b.x;
}
int Find(int v) {
return par[v] = (par[v] == v ? v : Find(par[v]));
}
bool uni(int p, int q){
p = Find(p), q = Find(q);
if (p == q) return 0;
par[q] = p; return 1;
}
void dfs(int v, int p, int s, int D) {
d[s][v] = D;
for (int i : g[v]) {
if (i != p) {
dfs(i, v, s, max(D, G[v][i]));
}
}
}
main() {
#ifdef IZI_KATKA
assert(freopen("input", "r", stdin));
assert(freopen("output", "w", stdout));
#endif
int n = readInt(), m = readInt();
int w = readInt(), h = readInt();
for (int i = 1; i <= n+4; i++) {
par[i] = i;
}
for (int i = 1; i <= n; i++) {
cin >> a[i].x >> a[i].y >> a[i].r;
}
for (int i = 1; i <= n; i++) {
for (int j = 1; j<= n; j++) {
if (i == j) continue;
double Z = dist(i, j) - (a[i].r + a[j].r);
G[i][j] = G[j][i] = (int)floor(Z / 2 + eps);
}
}
for (int i = 1; i <= n; i++) {
G[i][n+1] = G[n+1][i] = (a[i].y - a[i].r) / 2;
G[i][n+2] = G[n+2][i] = (a[i].x - a[i].r) / 2;
G[i][n+3] = G[n+3][i] = (w - a[i].r - a[i].x) / 2;
G[i][n+4] = G[n+4][i] = (h - a[i].r - a[i].y) / 2;
}
for (int i = 1; i <= 4; i++) {
for (int j = 1; j <= 4; j++) {
if (i != j) G[n+i][n+j] = MOD;
}
}
for(int i = 1; i<=n+4; i++){
for(int j = 1; j < i; j++){
v.push_back({i, j, G[i][j]});
}
}
sort(v.begin(), v.end(), cmp);
for (auto &i : v) {
if (uni(i.s, i.e)) {
g[i.s].pb(i.e);
g[i.e].pb(i.s);
}
}
for (int i = n + 1; i <= n + 4; i++) {
dfs(i, 0, i, 0);
}
ans[0][0] = ans[1][1] = ans[2][2] = ans[3][3] = 1e9;
ans[0][1] = ans[1][0] = min(d[n+1][n+2], min(d[n+1][n+3], d[n+1][n+4]));
ans[0][2] = ans[2][0] = min(min(d[n+1][n+2], d[n+1][n+4]), min(d[n+3][n+2], d[n+3][n+4]));
ans[0][3] = ans[3][0] = min(d[n+2][n+1], min(d[n+2][n+3], d[n+2][n+4]));
ans[1][2] = ans[2][1] = min(d[n+3][n+1], min(d[n+3][n+2], d[n+3][n+4]));
ans[1][3] = ans[3][1] = min(min(d[n+1][n+3], d[n+1][n+4]), min(d[n+2][n+3], d[n+2][n+4]));
ans[2][3] = ans[3][2] = min(d[n+4][n+1], min(d[n+4][n+2], d[n+4][n+3]));
while(m--) {
int r = readInt(), e = readInt();
for(int i = 1; i <= 4; i++){
if(ans[e-1][i-1] >= r){
putchar(i + '0');
}
}
puts("");
}
return 0;
}
Compilation message
park.cpp:124:6: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
main() {
^
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
745 ms |
84880 KB |
Output is correct |
| 2 |
Correct |
718 ms |
84880 KB |
Output is correct |
| 3 |
Correct |
715 ms |
85072 KB |
Output is correct |
| 4 |
Correct |
721 ms |
85076 KB |
Output is correct |
| 5 |
Correct |
704 ms |
85124 KB |
Output is correct |
| 6 |
Correct |
729 ms |
85300 KB |
Output is correct |
| 7 |
Correct |
691 ms |
85416 KB |
Output is correct |
| 8 |
Correct |
712 ms |
85416 KB |
Output is correct |
| 9 |
Correct |
3 ms |
85416 KB |
Output is correct |
| 10 |
Incorrect |
2 ms |
85416 KB |
Output isn't correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
26 ms |
85416 KB |
Output is correct |
| 2 |
Correct |
24 ms |
85416 KB |
Output is correct |
| 3 |
Correct |
23 ms |
85416 KB |
Output is correct |
| 4 |
Correct |
24 ms |
85416 KB |
Output is correct |
| 5 |
Correct |
25 ms |
85416 KB |
Output is correct |
| 6 |
Correct |
26 ms |
85416 KB |
Output is correct |
| 7 |
Incorrect |
28 ms |
85416 KB |
Output isn't correct |
| 8 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
745 ms |
84880 KB |
Output is correct |
| 2 |
Correct |
718 ms |
84880 KB |
Output is correct |
| 3 |
Correct |
715 ms |
85072 KB |
Output is correct |
| 4 |
Correct |
721 ms |
85076 KB |
Output is correct |
| 5 |
Correct |
704 ms |
85124 KB |
Output is correct |
| 6 |
Correct |
729 ms |
85300 KB |
Output is correct |
| 7 |
Correct |
691 ms |
85416 KB |
Output is correct |
| 8 |
Correct |
712 ms |
85416 KB |
Output is correct |
| 9 |
Correct |
3 ms |
85416 KB |
Output is correct |
| 10 |
Incorrect |
2 ms |
85416 KB |
Output isn't correct |
