#include <bits/stdc++.h>
#define DIM 2010
#define INF 1000000000
using namespace std;
struct tree{
int x,y,r;
};
tree v[DIM];
vector <int> L[DIM];
deque <int> d;
int a[5][5],viz[DIM];
int n,m,i,j,x,y,r,c,w,h;
int overlap (int i, int val, int c){
if (c == 1){
if (v[i].x - v[i].r - val <= 0)
return 1;
} else {
if (c == 2){
if (v[i].y - v[i].r - val <= 0)
return 1;
} else {
if (c == 3){
if (v[i].x + v[i].r + val >= w)
return 1;
} else {
if (v[i].y + v[i].r + val >= h)
return 1;
}}}
return 0;
}
int intersectie (int x, int y, int r, int x2, int y2, int r2){
if (1LL * (r + r2) * (r + r2) > 1LL * (x - x2) * (x - x2) + 1LL * (y - y2) * (y - y2))
return 1;
return 0;
}
int verif (int val, int c1, int c2){
for (int i=1;i<=n;i++)
L[i].clear();
for (int i=1;i<=n;i++)
for (int j=i+1;j<=n;j++){
if (intersectie (v[i].x,v[i].y,v[i].r + val, v[j].x,v[j].y,v[j].r + val)){
L[i].push_back(j);
L[j].push_back(i);
}}
/// gasesc punctele de start
memset (viz,0,sizeof viz);
int ok = 0;
for (int i=1;i<=n;i++){
if (viz[i])
continue;
if (!overlap(i,val,c1)) /// nu poate fi punct de start
continue;
d.clear();
d.push_back(i);
viz[i] = 1;
while (!d.empty()){
int nod = d.front();
d.pop_front();
for (auto vecin : L[nod]){
if (!viz[vecin]){
d.push_back(vecin);
viz[vecin] = 1;
if (overlap(vecin,val,c2)){
ok = 1;
break;
}}}
if (ok)
break;
}
if (ok)
break;
}
return ok;
}
int main (){
//ifstream cin ("date.in");
//ofstream cout ("date.out");
cin>>n>>m>>w>>h;
for (i=1;i<=n;i++)
cin>>v[i].x>>v[i].y>>v[i].r;
/// raza minima cu care pot sa maresc cercurile a.i. sa blochez o bucata
for (i=1;i<=4;i++)
for (j=i+1;j<=4;j++){
int st = 1, dr = INF, sol = 0;
while (st <= dr){
int mid = (st+dr)>>1;
if (verif (mid,i,j)){
sol = mid;
dr = mid-1;
} else st = mid+1;
}
a[i][j] = sol;
}
for (;m--;){
cin>>r>>c;
if (c == 1){
cout<<1;
if (!(a[1][2] <= r || a[2][4] <= r || a[2][3] <= r))
cout<<2;
if (!(a[1][2] <= r || a[2][4] <= r || a[3][4] <= r || a[1][3] <= r))
cout<<3;
if (!(a[1][2] <= r || a[1][3] <= r || a[1][4] <= r))
cout<<4;
} else {
if (c == 2){
if (!(a[1][2] <= r || a[2][4] <= r || a[2][3] <= r))
cout<<1;
cout<<2;
if (!(a[2][3] <= r || a[1][3] <= r || a[3][4] <= r))
cout<<3;
if (!(a[2][3] <= r || a[1][4] <= r || a[1][3] <= r || a[2][4] <= r))
cout<<4;
} else {
if (c == 3){
if (!(a[1][2] <= r || a[2][4] <= r || a[3][4] <= r || a[1][3] <= r))
cout<<1;
if (!(a[2][3] <= r || a[1][3] <= r || a[3][4] <= r))
cout<<2;
cout<<3;
if (!(a[3][4] <= r || a[1][4] <= r || a[2][4] <= r))
cout<<4;
} else { /// c == 4
if (!(a[1][2] <= r || a[1][3] <= r || a[1][4] <= r))
cout<<1;
if (!(a[2][3] <= r || a[1][4] <= r || a[1][3] <= r || a[2][4] <= r))
cout<<2;
if (!(a[3][4] <= r || a[1][4] <= r || a[2][4] <= r))
cout<<3;
cout<<4;
}
}
}
cout<<"\n";
}
return 0;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1804 ms |
17404 KB |
Output is correct |
| 2 |
Correct |
1799 ms |
17400 KB |
Output is correct |
| 3 |
Incorrect |
1830 ms |
17244 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
315 ms |
2040 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1804 ms |
17404 KB |
Output is correct |
| 2 |
Correct |
1799 ms |
17400 KB |
Output is correct |
| 3 |
Incorrect |
1830 ms |
17244 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
