Submission #291634

#	Time	Username	Problem	Language	Result	Execution time	Memory
291634		TadijaSebez	Fences (JOI18_fences)	C++11	100 / 100	714 ms	4328 KiB

fences

#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;
const ldb eps=1e-9;

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)>0)==(side(P,q.b)>0))return 0;
	line Q=line(q.a,q.b);
	if((side(Q,p.a)>0)==(side(Q,p.b)>0))return 0;
	return 1;
}
bool chk(pt a,int S){return a.x<S-eps&&a.x>-S+eps&&a.y<S-eps&&a.y>-S+eps;}
bool has(ldb l1,ldb r1,ldb l2,ldb r2){return max(l1,l2)+eps<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+eps&&p.a.y<S-eps&&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+eps<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,xb.b))^sec(ray,seg(xb.b,a[j].a)));
				AddEdge(i<<1,j<<1|1,dist(xb.a,xb.b),sec(ray,seg(a[i].a,xb.b))^sec(ray,seg(xb.b,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,xb.b))^sec(ray,seg(xb.b,a[j].a)));
				AddEdge(i<<1|1,j<<1|1,dist(xb.a,xb.b),sec(ray,seg(a[i].b,xb.b))^sec(ray,seg(xb.b,a[j].b)));
			}
		}
		AddEdge(i<<1,i<<1|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 (stderr)

fences.cpp: In constructor 'edge::edge(int, long double, int)':
fences.cpp:87:8: warning: 'edge::v' will be initialized after [-Wreorder]
   87 |  int f,v;
      |        ^
fences.cpp:86:6: warning:   'long double edge::w' [-Wreorder]
   86 |  ldb w;
      |      ^
fences.cpp:88:2: warning:   when initialized here [-Wreorder]
   88 |  edge(int a,ldb b,int c):v(a),w(b),f(c){}
      |  ^~~~
fences.cpp: In function 'int main()':
fences.cpp:118:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  118 |  scanf("%i %i",&n,&S);
      |  ~~~~~^~~~~~~~~~~~~~~
fences.cpp:121:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  121 |   scanf("%i %i %i %i",&a,&b,&c,&d);
      |   ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 18 / 18
• Subtask 2: 33 / 33
• Subtask 3: 49 / 49