#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 - 2 * val < 0)
return 1;
} else {
if (c == 2){
if (v[i].y - v[i].r - 2 * val < 0)
return 1;
} else {
if (c == 3){
if (v[i].x + v[i].r + 2 * val > w)
return 1;
} else {
if (v[i].y + v[i].r + 2 * 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;
if (overlap(i,val,c2)){
ok = 1;
break;
}
while (!d.empty()){
int nod = d.front();
d.pop_front();
for (int j=1;j<=n;j++){
if (!intersectie (v[nod].x,v[nod].y,v[nod].r + val, v[j].x,v[j].y,v[j].r + val))
continue;
if (!viz[j]){
d.push_back(j);
viz[j] = 1;
if (overlap(j,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 = 0, 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 |
634 ms |
504 KB |
Output is correct |
| 2 |
Correct |
910 ms |
504 KB |
Output is correct |
| 3 |
Correct |
617 ms |
436 KB |
Output is correct |
| 4 |
Correct |
768 ms |
384 KB |
Output is correct |
| 5 |
Correct |
875 ms |
384 KB |
Output is correct |
| 6 |
Correct |
697 ms |
384 KB |
Output is correct |
| 7 |
Correct |
1559 ms |
440 KB |
Output is correct |
| 8 |
Correct |
1719 ms |
504 KB |
Output is correct |
| 9 |
Correct |
5 ms |
384 KB |
Output is correct |
| 10 |
Correct |
5 ms |
384 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
298 ms |
736 KB |
Output is correct |
| 2 |
Correct |
298 ms |
888 KB |
Output is correct |
| 3 |
Correct |
299 ms |
760 KB |
Output is correct |
| 4 |
Correct |
313 ms |
964 KB |
Output is correct |
| 5 |
Correct |
297 ms |
760 KB |
Output is correct |
| 6 |
Correct |
304 ms |
760 KB |
Output is correct |
| 7 |
Correct |
293 ms |
632 KB |
Output is correct |
| 8 |
Correct |
289 ms |
632 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
634 ms |
504 KB |
Output is correct |
| 2 |
Correct |
910 ms |
504 KB |
Output is correct |
| 3 |
Correct |
617 ms |
436 KB |
Output is correct |
| 4 |
Correct |
768 ms |
384 KB |
Output is correct |
| 5 |
Correct |
875 ms |
384 KB |
Output is correct |
| 6 |
Correct |
697 ms |
384 KB |
Output is correct |
| 7 |
Correct |
1559 ms |
440 KB |
Output is correct |
| 8 |
Correct |
1719 ms |
504 KB |
Output is correct |
| 9 |
Correct |
5 ms |
384 KB |
Output is correct |
| 10 |
Correct |
5 ms |
384 KB |
Output is correct |
| 11 |
Correct |
298 ms |
736 KB |
Output is correct |
| 12 |
Correct |
298 ms |
888 KB |
Output is correct |
| 13 |
Correct |
299 ms |
760 KB |
Output is correct |
| 14 |
Correct |
313 ms |
964 KB |
Output is correct |
| 15 |
Correct |
297 ms |
760 KB |
Output is correct |
| 16 |
Correct |
304 ms |
760 KB |
Output is correct |
| 17 |
Correct |
293 ms |
632 KB |
Output is correct |
| 18 |
Correct |
289 ms |
632 KB |
Output is correct |
| 19 |
Correct |
1191 ms |
1836 KB |
Output is correct |
| 20 |
Correct |
1055 ms |
2040 KB |
Output is correct |
| 21 |
Correct |
938 ms |
1828 KB |
Output is correct |
| 22 |
Correct |
803 ms |
1912 KB |
Output is correct |
| 23 |
Correct |
1135 ms |
1784 KB |
Output is correct |
| 24 |
Correct |
1938 ms |
1892 KB |
Output is correct |
