#include<bits/stdc++.h>
using namespace std;
long double dist(pair<long double,long double>a,pair<long double,long double>b){
return hypot((a.first-b.first),(a.second-b.second))/2;
}
long double counts=INT_MAX;
vector<vector<pair<long double,long double>>>adj(1001);
void dfs(int j ,vector<int>visited,int cnt,long double ans){
if (cnt==visited.size()){
counts=min(ans,counts);
return ;
}
if (ans>counts)return;
visited[j]++;
for (auto x:adj[j]){
if (visited[x.first]<2){
dfs(x.first,visited,cnt+(visited[x.first]==0),max(ans,x.second));
}
}
}
vector<pair<long double,long double>>arr(1001);
int main(){
ios_base::sync_with_stdio(false);
cin.tie(NULL);
int n;cin>>n;
for (int i = 0;i<n;++i){
cin>>arr[i].first>>arr[i].second;
}
for (int i = 0;i<n;++i){
for (int j = i+1;j<n;++j){
adj[i].push_back({j,dist(arr[i],arr[j])});
adj[j].push_back({i,dist(arr[i],arr[j])});
}
}
vector<int>visited(n,false);
dfs(0,visited,1,INT_MIN);
cout<<fixed<<setprecision(15)<<counts;
return 0;}
Compilation message
odasiljaci.cpp: In function 'void dfs(int, std::vector<int>, int, long double)':
odasiljaci.cpp:9:9: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
9 | if (cnt==visited.size()){
| ~~~^~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
332 KB |
Output is correct |
| 2 |
Execution timed out |
1084 ms |
332 KB |
Time limit exceeded |
| 3 |
Execution timed out |
1074 ms |
460 KB |
Time limit exceeded |
| 4 |
Execution timed out |
1090 ms |
716 KB |
Time limit exceeded |
| 5 |
Execution timed out |
1090 ms |
844 KB |
Time limit exceeded |
| 6 |
Execution timed out |
1084 ms |
10508 KB |
Time limit exceeded |
| 7 |
Execution timed out |
1092 ms |
10564 KB |
Time limit exceeded |
| 8 |
Execution timed out |
1093 ms |
26800 KB |
Time limit exceeded |
| 9 |
Execution timed out |
1094 ms |
40644 KB |
Time limit exceeded |
| 10 |
Execution timed out |
1094 ms |
40624 KB |
Time limit exceeded |
