Submission #565187

#	Time	Username	Problem	Language	Result	Execution time	Memory
565187		errorgorn	Fences (JOI18_fences)	C++17	51 / 100	916 ms	2004 KiB

fences

#include <bits/stdc++.h>
using namespace std;

#define int long long
#define ii pair<int,int>
#define fi first
#define se second

#define puf push_front
#define pof pop_front
#define pub push_back
#define pob pop_back
#define lb lower_bound
#define ub upper_bound

#define rep(x,s,e) for (int x=(s)-((s)>(e));x!=(e)-((s)>(e));((s)<(e))?x++:x--)
#define all(x) (x).begin(),(x).end()
#define sz(x) (int) (x).size()

mt19937 rng(chrono::system_clock::now().time_since_epoch().count());

const double EPS=1e-9;
const double TAU=acos(0)*4;

struct vec{
	double x,y;
};

vec add(vec i,vec j){
	return {i.x+j.x,i.y+j.y};
}

vec sub(vec i,vec j){
	return {i.x-j.x,i.y-j.y};
};

vec mul(double lambda,vec i){
	return {i.x*lambda,i.y*lambda};
};

double dist(vec i,vec j){
	double dx=i.x-j.x;
	double dy=i.y-j.y;
	return sqrt(dx*dx+dy*dy);
}

int n;
double k;
int arr[110][4];

vector<vec> p; //stores all points
vector<double> angle;

double diff(double i,double j){
	double res=i-j;
	while (res<-TAU/2) res+=TAU;
	while (res>TAU/2) res-=TAU;
	return res;
}

int count(double i){
	return floor(i/TAU+0.5);
}

#define id pair<int,double>
#define dii pair<double,ii>
double w[10005][5];
vector<id> al[10005];

priority_queue<dii,vector<dii>,greater<dii> > pq;

bool inter(vec i,vec j,vec a,vec b){
	//i.x + j.x*L1 = a.x + b.x*L2
	//i.y + j.y*L1 = a.y + b.y*L2
	
	//j.x * L1 - b.x * L2 = a.x - i.x
	//j.y * L1 - b.y * L2 = a.y - i.y
	
	//check that L1,L2 in [0,1]
	
	vector<double> v = {
		a.x - i.x,
		a.y - i.y
	};
	
	vector<vector<double> > mat = {
		{j.x,-b.x},
		{j.y,-b.y}
	};
	
	double det=mat[0][0]*mat[1][1]-mat[0][1]*mat[1][0];
	if (abs(det)<=1e-9) return false;
	
	vector<vector<double> > imat = {
		{mat[1][1],-mat[0][1]},
		{-mat[1][0],mat[0][0]}
	};
	rep(x,0,2) rep(y,0,2) imat[x][y]/=det;
	
	rep(x,0,2){
		double res=0;
		rep(y,0,2){
			res+=imat[x][y]*v[y];
		}
		if (res<0 || 1<res) return false;
	}
	return true;
}

bool ok(vec i,vec j){
	vector<vec> v={  {-k+2*EPS,-k+EPS},{-k+EPS,k-2*EPS},{k-2*EPS,k-EPS},{k-EPS,-k+2*EPS} };
	vector<vec> v2={ {-k+2*EPS,k-EPS},{k-EPS,k-2*EPS},{k-2*EPS,-k+EPS},{-k+EPS,-k+2*EPS} };
	
	rep(x,0,4){
		if (inter(i,sub(j,i),v[x],sub(v2[x],v[x]))) return false;
	}
	return true;
}

signed main(){
	cin.tie(0);
	cout.tie(0);
	cin.sync_with_stdio(false);
	
	cin>>n>>k;
	rep(x,0,n) rep(y,0,4) cin>>arr[x][y];
	rep(x,0,4) rep(y,0,4){
		if (x==3 || (x && (x+y)%2==0)) arr[n+x][y]=-k;
		else arr[n+x][y]=k;
	}
	n+=4;
	
	//rep(x,0,n){
		//rep(y,0,4) cout<<arr[x][y]<<" "; cout<<endl;
	//}
	
	rep(x,0,n) p.pub({(double)arr[x][0],(double)arr[x][1]});
	rep(x,0,n) p.pub({(double)arr[x][2],(double)arr[x][3]});
	rep(x,0,n){
		al[x].pub({x+n,0});
		al[x+n].pub({x,0});
	}
	
	double ans=8*k;
	
	rep(x,0,n) rep(y,x+1,n){
		vec temp[4];
		vec temp2[4];
		
		double best=1e18;
		int idx=-1;
		
		rep(z,0,4){
			if (z>=2) swap(x,y);
			
			if (z%2==0) temp2[z]=p[x];
			else temp2[z]=p[x+n];
			
			vec base=p[y];
			vec dir=sub(p[y+n],p[y]);
			
			double lo=0,hi=1;
			rep(x,0,150){
				double mi1=lo+(hi-lo)/3,mi2=lo+2*(hi-lo)/3;
				
				if (dist(add(base,mul(mi1,dir)),temp2[z])<dist(add(base,mul(mi2,dir)),temp2[z])){
					hi=mi2;
				}
				else{
					lo=mi1;
				}
			}
			
			temp[z]=add(base,mul(lo,dir));
			double curr=dist(temp2[z],temp[z]);
			if (curr<best){
				best=curr;
				idx=z;
			}
			
			if (z>=2) swap(x,y);
		}
		
		if (ok(temp[idx],temp2[idx])){
			//cout<<x<<" "<<y<<" "<<best<<" "<<idx<<endl;
			//cout<<temp[idx].x<<" "<<temp[idx].y<<endl;
			//cout<<temp2[idx].x<<" "<<temp2[idx].y<<endl;
			//rep(z,0,4) cout<<arr[x][z]<<" "; cout<<endl;
			//rep(z,0,4) cout<<arr[y][z]<<" "; cout<<endl;
			//cout<<endl;
			
			//cout<<"cunny"<<endl;
			int IDX1=sz(p),IDX2;
			p.pub(temp[idx]);
			
			if (idx==0) IDX2=x;
			if (idx==1) IDX2=x+n;
			if (idx==2) IDX2=y;
			if (idx==3) IDX2=y+n;
			
			//cout<<temp2[idx].x<<" "<<temp2[idx].y<<endl;
			//cout<<p[IDX2].x<<" "<<p[IDX2].y<<endl;
			
			al[IDX1].pub({IDX2,best});
			al[IDX2].pub({IDX1,best});
			
			if (idx<2) IDX2=y;
			else IDX2=x;
			al[IDX1].pub({IDX2,0});
			al[IDX2].pub({IDX1,0});
		}
	}
	
	rep(x,0,sz(p)){
		angle.pub(atan2(p[x].x,p[x].y)+TAU/2);
		//cout<<x<<" "<<p[x].x<<" "<<p[x].y<<" "<<angle[x]<<endl;
	}
	
	rep(x,0,n){
		rep(y,0,sz(p)) rep(z,0,5) w[y][z]=1e18;
		
		w[x][2]=0;
		pq.push({w[x][2],ii(x,2)});
		
		while (!pq.empty()){
			double weight;
			ii u;
			tie(weight,u)=pq.top(),pq.pop();
			if (w[u.fi][u.se]!=weight) continue;
			
			double angle1=diff(angle[x],angle[u.fi])+TAU*u.se;
			
			for (auto [it,w2]:al[u.fi]){
				int it2=count(angle1+diff(angle[u.fi],angle[it])-diff(angle[x],angle[it]));
				if (it2<0 || 4<it2) continue;
				if (w[it][it2]>weight+w2){
					w[it][it2]=weight+w2;
					pq.push({w[it][it2],ii(it,it2)});
				}
			}
		}
		
		//cout<<x<<" "<<w[x][3]<<endl;
		ans=min(ans,w[x][3]);
	}
	
	cout<<fixed<<setprecision(12)<<ans<<endl;
}

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