Submission #201542

#TimeUsernameProblemLanguageResultExecution timeMemory
201542gs18115Fences (JOI18_fences)C++14
18 / 100
5 ms504 KiB
#include<iostream> #include<iomanip> #include<vector> #include<cmath> #include<algorithm> #define ep emplace #define eb emplace_back #define fi first #define se second #define all(x) (x).begin(),(x).end() #define semicolon ; #define ryan bear using namespace std; typedef long long ll; typedef pair<int,int>pi; typedef pair<ll,ll>pl; typedef pair<double,double>pd; typedef pair<pd,pd>ln; const int inf=1e9+7; const ll INF=1e18; const double eps=1e-5; const ln xa(pd(0,0),pd(INF,0)); pd operator-(pd x,pd y) { return pd(x.fi-y.fi,x.se-y.se); } inline double ccw(pd x,pd y) { return x.fi*y.se-x.se*y.fi; } inline double sq(double x) { return x*x; } inline double abs(pd x) { return sqrt(sq(x.fi)+sq(x.se)); } inline double dist(pd x,pd y) { return sqrt(sq(x.fi-y.fi)+sq(x.se-y.se)); } inline double dot(pd x,pd y) { return x.fi*y.fi+x.se*y.se; } inline bool cross1(ln x,ln y) { bool xc=ccw(x.fi-y.fi,x.se-y.fi)*ccw(x.fi-y.se,x.se-y.se)<0; swap(x,y); bool yc=ccw(x.fi-y.fi,x.se-y.fi)*ccw(x.fi-y.se,x.se-y.se)<0; return xc&&yc; } inline bool cross2(ln x,ln y) { bool xc=ccw(x.fi-y.fi,x.se-y.fi)*ccw(x.fi-y.se,x.se-y.se)<eps; swap(x,y); bool yc=ccw(x.fi-y.fi,x.se-y.fi)*ccw(x.fi-y.se,x.se-y.se)<eps; return xc&&yc; } inline pd cut(ln x,double r) { return pd(x.fi.fi*(1-r)+x.se.fi*r,x.fi.se*(1-r)+x.se.se*r); } inline pd perp(pd x,ln y) { double rs=0; double re=1; while(re-rs>eps) { double r1=(rs*2+re)/3; double r2=(rs+re*2)/3; if(dist(x,cut(y,r1))<dist(x,cut(y,r2))) re=r2; else rs=r1; } return cut(y,rs); } double d[505][505]; inline void init(int n) { for(int i=0;i<n;i++) for(int j=0;j<n;j++) d[i][j]=INF; for(int i=0;i<n;i++) d[i][i]=0; return; } inline void app(int i,int j,double y) { d[i][j]=min(d[i][j],y); d[j][i]=min(d[j][i],y); return; } vector<ln>rs; inline void app(int i,int j,int sz,pd x,pd y) { for(ln&t:rs) if(cross1(t,ln(x,y))) return; double nd=dist(x,y); if(cross1(xa,ln(x,y))) app(i,j+sz,nd),app(i+sz,j,nd); else app(i,j,nd),app(i+sz,j+sz,nd); return; } inline void floyd(int n) { for(int k=0;k<n;k++) for(int i=0;i<n;i++) for(int j=0;j<n;j++) d[i][j]=min(d[i][j],d[i][k]+d[k][j]); return; } int main() { ios_base::sync_with_stdio(false); cin.tie(nullptr); int n; double s; cin>>n>>s; vector<ln>v; vector<pd>rp; rp.eb(s,s),rp.eb(-s,s),rp.eb(-s,-s),rp.eb(s,-s); for(int i=0;i<4;i++) for(int j=i+1;j<4;j++) rs.eb(rp[i],rp[j]); for(pd&t:rp) v.eb(t,t); for(int i=0;i<n;i++) { pd x,y; cin>>x.fi>>x.se>>y.fi>>y.se; if(x.se<0) swap(x,y); if(cross2(xa,ln(x,y))) { v.eb(x,cut(ln(x,y),x.se/(x.se-y.se))); v.back().se.se+=eps; v.eb(cut(ln(x,y),x.se/(x.se-y.se)),y); v.back().fi.se-=eps; } else v.eb(x,y); } n=v.size(); init(n*2); for(int i=0;i<n;i++) { for(int j=i+1;j<n;j++) { app(i,j,n,v[i].fi,v[j].fi); app(i,j,n,v[i].fi,v[j].se); app(i,j,n,v[i].se,v[j].fi); app(i,j,n,v[i].se,v[j].se); app(i,j,n,v[i].fi,perp(v[i].fi,v[j])); app(i,j,n,v[i].se,perp(v[i].se,v[j])); app(i,j,n,v[j].fi,perp(v[j].fi,v[i])); app(i,j,n,v[j].se,perp(v[j].se,v[i])); } } floyd(n*2); double m=INF; for(int i=0;i<n;i++) m=min(m,d[i][i+n]); cout<<fixed<<setprecision(12)<<m<<endl; return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...