Submission #4625930
Source Code Expand
#include <bits/stdc++.h>
using namespace std;
typedef pair<int,int > pp;
typedef long long ll;
#define sz(x) (int)x.size()
int const N=3e5+10,oo=1e9;
ll const OO=2e18;
double const eps=1e-8,PI=acos(-1);
int mod=oo+7;
struct circle{
int x,y,r;
circle(){};
circle(int x,int y,int r):x(x),y(y),r(r){}
};
int n;
int a,b,c,d;
circle all[1001];
priority_queue<pair<double,int > > q;
double cost[1001];
bool vis[1001];
double dist(pp a,pp b){
return sqrt((a.first-b.first)*(a.first-b.first)+
(a.second-b.second)*(a.second-b.second));
}
double distc(int i,int j){
double dd=dist({all[i].x,all[i].y},{all[j].x,all[j].y});
dd-=all[i].r+all[j].r;
if(dd<0)dd=0;
return dd;
}
int main(){
ios::sync_with_stdio(0);
cin.tie(0);
cin>>a>>b>>c>>d;
cin>>n;
for(int i=0;i<n;i++){
cost[i]=OO;
int x,y,r;
cin>>x>>y>>r;
all[i]=circle(x,y,r);
}
double mn=dist({a,b},{c,d});
for(int i=0;i<n;i++){
double dd=dist({a,b},{all[i].x,all[i].y});
if(dd<=all[i].r){
q.push({0,i});
cost[i]=0;
}else {
dd-=all[i].r;
q.push({-dd,i});
cost[i]=dd;
}
}
while(!q.empty()){
auto cur=q.top();q.pop();
double d=-cur.first;
int idx=cur.second;
if(vis[idx])continue;
vis[idx]=1;
for(int i=0;i<n;i++){
if(i==idx)continue;
double need=distc(idx,i);
if(!vis[i]&&cost[i]>need+d){
cost[i]=need+d;
q.push({-cost[i],i});
}
}
}
for(int i=0;i<n;i++)mn=min(mn,max(0.0,dist({c,d},{all[i].x,all[i].y})-all[i].r)+cost[i]);
cout<<fixed<<setprecision(10)<<mn<<'\n';
return 0;
}
Submission Info
Submission Time |
|
Task |
C - Boxes and Candies |
User |
abo_od303 |
Language |
C++14 (GCC 5.4.1) |
Score |
0 |
Code Size |
1776 Byte |
Status |
RE |
Exec Time |
99 ms |
Memory |
256 KB |
Judge Result
Set Name |
Sample |
All |
Score / Max Score |
0 / 0 |
0 / 300 |
Status |
|
|
Set Name |
Test Cases |
Sample |
0_00.txt, 0_01.txt, 0_02.txt, 0_03.txt |
All |
0_00.txt, 0_01.txt, 0_02.txt, 0_03.txt, 1_00.txt, 1_01.txt, 1_02.txt, 1_03.txt, 1_04.txt, 1_05.txt, 1_06.txt, 1_07.txt, 1_08.txt, 1_09.txt, 1_10.txt, 1_11.txt, 1_12.txt, 1_13.txt, 1_14.txt, 1_15.txt |
Case Name |
Status |
Exec Time |
Memory |
0_00.txt |
WA |
1 ms |
256 KB |
0_01.txt |
WA |
1 ms |
256 KB |
0_02.txt |
WA |
1 ms |
256 KB |
0_03.txt |
WA |
1 ms |
256 KB |
1_00.txt |
WA |
1 ms |
256 KB |
1_01.txt |
WA |
1 ms |
256 KB |
1_02.txt |
WA |
1 ms |
256 KB |
1_03.txt |
WA |
1 ms |
256 KB |
1_04.txt |
WA |
1 ms |
256 KB |
1_05.txt |
WA |
1 ms |
256 KB |
1_06.txt |
RE |
96 ms |
256 KB |
1_07.txt |
RE |
97 ms |
256 KB |
1_08.txt |
RE |
97 ms |
256 KB |
1_09.txt |
RE |
96 ms |
256 KB |
1_10.txt |
RE |
99 ms |
256 KB |
1_11.txt |
RE |
97 ms |
256 KB |
1_12.txt |
RE |
99 ms |
256 KB |
1_13.txt |
RE |
95 ms |
256 KB |
1_14.txt |
RE |
96 ms |
256 KB |
1_15.txt |
RE |
96 ms |
256 KB |