/// isA AC
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
void ACPLS()
{
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
}
#define tc \
int tttttt,subtask; \
cin >> tttttt /*>> subtask*/; \
while (tttttt--)
#define sumrange(l, r, arr) (l == 0 ? arr[r] : arr[r] - arr[l - 1])
#define all(v) v.begin(), v.end()
bool touch(long double x1, long double y1, long double x2,
long double y2, long double r1, long double r2)
{
long double distSq = (x1 - x2) * (x1 - x2) +
(y1 - y2) * (y1 - y2);
long double radSumSq = (r1 + r2) * (r1 + r2);
if (radSumSq>=distSq)
return 1;
return 0;
}
vector<int>adj[(int)1e3+5];
vector<bool>vis(1e3+3,0);
vector<vector<short>>dp(1e3+3,vector<short>(1e3+3,-1));
bool dfs(int curnode,int m){
if(curnode==m)
return 1;
if(dp[curnode][m]!=-1)
return dp[curnode][m];
if(vis[curnode])
return 0;
vis[curnode]=1;
bool ret=0;
for(int child:adj[curnode]){
ret|=dfs(child,m);
}
return dp[curnode][m]=ret;
}
int n;
pair<long double,long double> a[(int)1e3+5];
bool check(long double r){
for(int i = 0; i <= 1e3; i++)
adj[i]=vector<int>(1e3+3);
vis=vector<bool>(1e3+3,0);
dp=vector<vector<short>>(1e3+3,vector<short>(1e3+3,-1));
for(int i = 0; i < n; i++){
for(int j = i+1; j < n; j++){
if(touch(a[i].first,a[i].second,
a[j].first,a[j].second,r,r)){
adj[i].push_back(j);
adj[j].push_back(i);
}
}
}
bool ok=1;
for(int i = 0; i < n; i++){
for(int j = i+1; j < n; j++){
if(dp[i][j]!=-1)
ok&=dp[i][j];
vis=vector<bool>(1e3+3,0);
ok&=dfs(i,j);
}
}
return ok;
}
int main()
{
ACPLS();
cin>>n;
for(int i = 0; i < n; i++)
cin>>a[i].first>>a[i].second;
double lo=0,hi=1e9,ans=hi;
int it=0;
while(it<60){
double mid = (lo+hi)*0.5;
if(check(mid)){
ans=mid;
hi=mid;
}
else lo=mid;
++it;
}
cout<<fixed<<setprecision(6);
cout<<ans;
}
Compilation message
odasiljaci.cpp: In function 'bool dfs(int, int)':
odasiljaci.cpp:42:26: warning: suggest parentheses around assignment used as truth value [-Wparentheses]
42 | return dp[curnode][m]=ret;
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
75 ms |
8300 KB |
Output isn't correct |
| 2 |
Incorrect |
99 ms |
8312 KB |
Output isn't correct |
| 3 |
Incorrect |
848 ms |
8324 KB |
Output isn't correct |
| 4 |
Execution timed out |
1062 ms |
8432 KB |
Time limit exceeded |
| 5 |
Execution timed out |
1081 ms |
8516 KB |
Time limit exceeded |
| 6 |
Execution timed out |
1084 ms |
8268 KB |
Time limit exceeded |
| 7 |
Execution timed out |
1086 ms |
8268 KB |
Time limit exceeded |
| 8 |
Execution timed out |
1088 ms |
9292 KB |
Time limit exceeded |
| 9 |
Execution timed out |
1091 ms |
10188 KB |
Time limit exceeded |
| 10 |
Execution timed out |
1085 ms |
10316 KB |
Time limit exceeded |
