#include <bits/stdc++.h>
using namespace std;
#define ldb long double
#define mp make_pair
#define pb push_back
#define pii pair<int,int>
const ldb inf=1e9;
struct pt{ldb x,y;pt(ldb a=0,ldb b=0):x(a),y(b){}};
bool operator < (pt a,pt b){return mp(a.x,a.y)<mp(b.x,b.y);}
pt operator + (pt a,pt b){return pt(a.x+b.x,a.y+b.y);}
pt operator - (pt a,pt b){return pt(a.x-b.x,a.y-b.y);}
pt operator * (pt a,ldb b){return pt(a.x*b,a.y*b);}
pt operator / (pt a,ldb b){return pt(a.x/b,a.y/b);}
ldb cross(pt a,pt b){return a.x*b.y-a.y*b.x;}
ldb dot(pt a,pt b){return a.x*b.x+a.y*b.y;}
ldb sq(pt a){return dot(a,a);}
ldb abs(pt a){return sqrt(sq(a));}
ldb dist(pt a,pt b){return abs(a-b);}
pt perp(pt a){return pt(-a.y,a.x);}
struct line{pt v;ldb c;line(pt a,pt b):v(b-a),c(cross(v,a)){}};
ldb side(line a,pt b){return a.c-cross(a.v,b);}
ldb offs(line a,pt b){return dot(a.v,b);}
bool proj_on(line l,pt a,pt b,pt c){if(offs(l,a)>offs(l,c))swap(a,c);return offs(l,a)<=offs(l,b)&&offs(l,b)<=offs(l,c);}
pt drop(line a,pt b){return b+perp(a.v)/sq(a.v)*side(a,b);}
pt sec(line a,line b){return (b.v*a.c-a.v*b.c)/cross(a.v,b.v);}
struct seg{pt a,b;seg(){}seg(pt x,pt y):a(x),b(y){}};
bool operator < (seg p,seg q){return dist(p.a,p.b)<dist(q.a,q.b);}
seg drop(seg p,pt q){
line P(p.a,p.b);
if(proj_on(P,p.a,q,p.b))return seg(q,drop(P,q));
return seg(pt(0,0),pt(inf,0));
}
seg mn_dist(pt p,seg q){
seg ans=seg(p,q.a);
ans=min(ans,seg(p,q.b));
ans=min(ans,drop(q,p));
return ans;
}
seg mn_dist(seg p,seg q){
seg ans=seg(p.a,q.a);
ans=min(ans,seg(p.a,q.b));
ans=min(ans,seg(p.b,q.a));
ans=min(ans,seg(p.b,q.b));
ans=min(ans,drop(p,q.a));
ans=min(ans,drop(p,q.b));
ans=min(ans,drop(q,p.a));
ans=min(ans,drop(q,p.b));
return ans;
}
bool sec(seg p,seg q){
line P=line(p.a,p.b);
if(side(P,q.a)*side(P,q.b)>=0)return 0;
line Q=line(q.a,q.b);
if(side(Q,p.a)*side(Q,p.b)>=0)return 0;
return 1;
}
bool chk(pt a,int S){return a.x<S&&a.x>-S&&a.y<S&&a.y>-S;}
bool has(ldb l1,ldb r1,ldb l2,ldb r2){return max(l1,l2)<min(r1,r2);}
bool chk(seg p,int S){
if(p.a.x==p.b.x)swap(p.a.x,p.a.y),swap(p.b.x,p.b.y);
if(p.a.x==p.b.x)return chk(p.a,S);
if(p.a.x>p.b.x)swap(p.a,p.b);
if(p.a.y==p.b.y){
return p.a.y>-S&&p.a.y<S&&has(p.a.x,p.b.x,-S,S);
}
ldb lx=(-S-p.a.x)/(p.b.x-p.a.x);
ldb rx=(S-p.a.x)/(p.b.x-p.a.x);
if(lx>rx)swap(lx,rx);
ldb ly=(-S-p.a.y)/(p.b.y-p.a.y);
ldb ry=(S-p.a.y)/(p.b.y-p.a.y);
if(ly>ry)swap(ly,ry);
ldb L=max({lx,ly,(ldb)0});
ldb R=min({rx,ry,(ldb)1});
if(L<R)return 1;
return 0;
}
const int N=107;
int n,S;
seg a[N];
struct edge{
ldb w;
int f,v;
edge(int a,ldb b,int c):v(a),w(b),f(c){}
};
vector<edge> E[N*2];
void AddEdge(int u,int v,ldb w,int f){
E[u].pb(edge(v,w,f));
E[v].pb(edge(u,w,f));
}
ldb ans=inf,dst[N*2][2];
void Dijkstra(int x,int n){
priority_queue<pair<ldb,pii>> pq;
for(int i=1;i<=n;i++)dst[i][0]=dst[i][1]=inf;
dst[x][0]=0;
pq.push({0,{x,0}});
while(pq.size()){
ldb d=-pq.top().first;
pii u=pq.top().second;
pq.pop();
if(d!=dst[u.first][u.second])continue;
for(edge e:E[u.first]){
int v=e.v;
int f=e.f^u.second;
if(dst[v][f]>dst[u.first][u.second]+e.w){
dst[v][f]=dst[u.first][u.second]+e.w;
pq.push({-dst[v][f],{v,f}});
}
}
}
ans=min(ans,dst[x][1]);
}
int main(){
scanf("%i %i",&n,&S);
for(int i=1;i<=n;i++){
int a,b,c,d;
scanf("%i %i %i %i",&a,&b,&c,&d);
::a[i]=seg(pt(a,b),pt(c,d));
}
a[++n]=seg(pt(S,S),pt(S,S));
a[++n]=seg(pt(S,-S),pt(S,-S));
a[++n]=seg(pt(-S,S),pt(-S,S));
a[++n]=seg(pt(-S,-S),pt(-S,-S));
seg ray=seg(pt(0,0),pt(inf,1));
for(int i=1;i<=n;i++){
for(int j=1;j<=n;j++)if(i!=j){
seg xb=mn_dist(a[i].a,a[j]);
if(!chk(xb,S)){
AddEdge(i<<1,j<<1,dist(xb.a,xb.b),sec(ray,seg(a[i].a,a[j].a)));
AddEdge(i<<1,j<<1|1,dist(xb.a,xb.b),sec(ray,seg(a[i].a,a[j].b)));
}
xb=mn_dist(a[i].b,a[j]);
if(!chk(xb,S)){
AddEdge(i<<1|1,j<<1,dist(xb.a,xb.b),sec(ray,seg(a[i].b,a[j].a)));
AddEdge(i<<1|1,j<<1|1,dist(xb.a,xb.b),sec(ray,seg(a[i].b,a[j].b)));
}
}
AddEdge(i<<1,i<<1|1,0,sec(ray,a[i]));
E[i<<1].pb(edge(i<<1|1,0,sec(ray,a[i])));
E[i<<1|1].pb(edge(i<<1,0,sec(ray,a[i])));
}
for(int i=2;i<=n*2+1;i++)Dijkstra(i,n*2+1);
printf("%.10Lf\n",ans);
return 0;
}
Compilation message
fences.cpp: In constructor 'edge::edge(int, long double, int)':
fences.cpp:86:8: warning: 'edge::v' will be initialized after [-Wreorder]
86 | int f,v;
| ^
fences.cpp:85:6: warning: 'long double edge::w' [-Wreorder]
85 | ldb w;
| ^
fences.cpp:87:2: warning: when initialized here [-Wreorder]
87 | edge(int a,ldb b,int c):v(a),w(b),f(c){}
| ^~~~
fences.cpp: In function 'int main()':
fences.cpp:117:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
117 | scanf("%i %i",&n,&S);
| ~~~~~^~~~~~~~~~~~~~~
fences.cpp:120:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
120 | scanf("%i %i %i %i",&a,&b,&c,&d);
| ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
1 ms |
384 KB |
Output is correct |
| 2 |
Correct |
1 ms |
384 KB |
Output is correct |
| 3 |
Correct |
1 ms |
384 KB |
Output is correct |
| 4 |
Correct |
1 ms |
384 KB |
Output is correct |
| 5 |
Correct |
1 ms |
384 KB |
Output is correct |
| 6 |
Correct |
1 ms |
384 KB |
Output is correct |
| 7 |
Correct |
1 ms |
384 KB |
Output is correct |
| 8 |
Correct |
1 ms |
384 KB |
Output is correct |
| 9 |
Correct |
1 ms |
384 KB |
Output is correct |
| 10 |
Correct |
1 ms |
384 KB |
Output is correct |
| 11 |
Correct |
1 ms |
384 KB |
Output is correct |
| 12 |
Correct |
1 ms |
384 KB |
Output is correct |
| 13 |
Correct |
1 ms |
384 KB |
Output is correct |
| 14 |
Correct |
1 ms |
384 KB |
Output is correct |
| 15 |
Correct |
1 ms |
384 KB |
Output is correct |
| 16 |
Incorrect |
1 ms |
384 KB |
Output isn't correct |
| 17 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
1 ms |
384 KB |
Output is correct |
| 2 |
Correct |
1 ms |
384 KB |
Output is correct |
| 3 |
Correct |
1 ms |
384 KB |
Output is correct |
| 4 |
Correct |
1 ms |
384 KB |
Output is correct |
| 5 |
Correct |
1 ms |
384 KB |
Output is correct |
| 6 |
Correct |
1 ms |
384 KB |
Output is correct |
| 7 |
Correct |
1 ms |
384 KB |
Output is correct |
| 8 |
Correct |
1 ms |
384 KB |
Output is correct |
| 9 |
Correct |
1 ms |
384 KB |
Output is correct |
| 10 |
Correct |
1 ms |
384 KB |
Output is correct |
| 11 |
Correct |
1 ms |
384 KB |
Output is correct |
| 12 |
Correct |
1 ms |
384 KB |
Output is correct |
| 13 |
Correct |
1 ms |
384 KB |
Output is correct |
| 14 |
Correct |
1 ms |
384 KB |
Output is correct |
| 15 |
Correct |
1 ms |
384 KB |
Output is correct |
| 16 |
Incorrect |
1 ms |
384 KB |
Output isn't correct |
| 17 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
1 ms |
384 KB |
Output is correct |
| 2 |
Correct |
1 ms |
384 KB |
Output is correct |
| 3 |
Correct |
1 ms |
384 KB |
Output is correct |
| 4 |
Correct |
1 ms |
384 KB |
Output is correct |
| 5 |
Correct |
1 ms |
384 KB |
Output is correct |
| 6 |
Correct |
1 ms |
384 KB |
Output is correct |
| 7 |
Correct |
1 ms |
384 KB |
Output is correct |
| 8 |
Correct |
1 ms |
384 KB |
Output is correct |
| 9 |
Correct |
1 ms |
384 KB |
Output is correct |
| 10 |
Correct |
1 ms |
384 KB |
Output is correct |
| 11 |
Correct |
1 ms |
384 KB |
Output is correct |
| 12 |
Correct |
1 ms |
384 KB |
Output is correct |
| 13 |
Correct |
1 ms |
384 KB |
Output is correct |
| 14 |
Correct |
1 ms |
384 KB |
Output is correct |
| 15 |
Correct |
1 ms |
384 KB |
Output is correct |
| 16 |
Incorrect |
1 ms |
384 KB |
Output isn't correct |
| 17 |
Halted |
0 ms |
0 KB |
- |
