Submission #8829113

---

Source Code Expand

/*
貪欲
後ろから見る
DP
順位表をチェック
二分探索


*/
#pragma GCC optimize("Ofast")
#include<cstdio>
#include<cstdlib>
#include<algorithm>
#include<iostream>
#include<queue>
#include<vector>
#include <bitset>
#include <cmath>
#include <limits>
#include <iostream>
#include <map>
#include<tuple>
using namespace std;
#define INF 3e18+7
#define MAX 100000
#define MOD 1000000007
typedef long long ll;
typedef pair<double,int> P;
//typedef pair<pair<int,int>,int> p;
#define bit(n,k) ((n>>k)&1) /*nのk bit目*/
#define rad_to_deg(rad) (((rad)/2/M_PI)*360)
struct edge{ll to,cost,val;};
template<class T,class U>bool chmin(T&a,const U&b){if(a<=b)return false;a=b;return true;}
template<class T,class U>bool chmax(T&a,const U&b){if(a>=b)return false;a=b;return true;}
//__builtin_popcount(S);
//C.erase(unique(C.begin(),C.end()),C.end());

int S[110000],Z[110000];
int C[1100];


int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int N;
    ll sx,sy,tx,ty,x[1100],y[1100],r[1100];
    double d[1100];
    cin>>sx>>sy>>tx>>ty>>N;
    vector<P> V;
    for(int i=1;i<=N;i++){
        cin>>x[i]>>y[i]>>r[i];
        double t=sqrt((sx-x[i])*(sx-x[i])+(sy-y[i])*(sy-y[i]));
        t-=(r[i]);
        if(t<0) t=0;
        d[i]=t;
        V.push_back(P(t,i));
        //cout<<d[i]<<endl;
    }
    sort(V.begin(),V.end());
    int n;
    for(int i=0;i<=N-1;i++){
        int s;
        if(i==0) s=V[i].second;
        else s=n; 
        double m=INF;
        C[n]++;
        for(int j=1;j<=N;j++){
            if(C[j]) continue;

            int next=j;
            double t=sqrt( (x[s]-x[next])*(x[s]-x[next])+(y[s]-y[next])*(y[s]-y[next]) );
            t-=(r[s]+r[next]);
            if(t<0) t=0;
            chmin(d[next],d[s]+t);
            if(m>d[next]){
                m=d[next];
                n=next;
            }
        }
    }
    double ans=sqrt( (sx-tx)*(sx-tx)+(sy-ty)*(sy-ty) );
    for(int i=1;i<=N;i++){
        double t=sqrt( (x[i]-tx)*(x[i]-tx)+(y[i]-ty)*(y[i]-ty) );
        t-=r[i];
        if(t<0) t=0;
        chmin(ans,d[i]+t);
    }
    printf("%.15lf\n",ans);

}

Submission Info

Judge Result