Submission #1223773

#	Time	Username	Problem	Language	Result	Execution time	Memory
1223773		emptypringlescan	Fences (JOI18_fences)	C++17	51 / 100	265 ms	13592 KiB

fences

#include <bits/stdc++.h>
using namespace std;
long double eps=0.0000000001,eep=0.0001;
long double ptpt(pair<long double,long double> a,pair<long double,long double> b){
	long double ret= sqrt((a.first-b.first)*(a.first-b.first)+(a.second-b.second)*(a.second-b.second));
	assert(ret>=0);
	return ret;
}
bool online(pair<long double,long double> pt, pair<long double,long double> a, pair<long double,long double> b){
	long double d1=ptpt(pt,a),d2=ptpt(pt,b),d3=ptpt(a,b);
	return abs(d1+d2-d3)<eps;
}
pair<long double,pair<pair<long double,long double>,pair<long double,long double> > > shortdist(pair<long double,long double> pt, pair<long double,long double> a, pair<long double,long double> b){
	pair<long double,long double> d={b.first-a.first,b.second-a.second};
	if(abs(d.first)<eps&&abs(d.second)<eps){
		return {ptpt(pt,a),{pt,a}};
	}
	pair<long double,pair<pair<long double,long double>,pair<long double,long double> > > ret=min(make_pair(ptpt(pt,a),make_pair(pt,a)),make_pair(ptpt(pt,b),make_pair(pt,b)));
	long double t=(d.first*pt.first - d.first*a.first + d.second*pt.second - d.second*a.second)/(d.first*d.first + d.second*d.second);
	if(0-eps<=t && t<=1+eps){
		pair<long double,long double> ft={a.first+t*d.first,a.second+t*d.second};
		ret=min(ret,{ptpt(ft,pt),{ft,pt}});
	}
	return ret;
}
pair<long double,pair<pair<long double,long double>,pair<long double,long double> > > lnln(pair<long double,long double> x,pair<long double,long double> y, pair<long double,long double> a,pair<long double,long double> b){
	pair<long double,pair<pair<long double,long double>,pair<long double,long double> > > ret=min({shortdist(x,a,b),shortdist(y,a,b),shortdist(a,x,y),shortdist(b,x,y)});
	assert(ret.first>=0);
	return ret;
}
long double area(pair<long double,long double> a,pair<long double,long double> x, pair<long double,long double> y){
	return (x.first-a.first)*(x.second+a.second)+(y.first-x.first)*(y.second+x.second)+(a.first-y.first)*(a.second+y.second);
}
bool intersect(pair<long double,long double> a,pair<long double,long double> b,pair<long double,long double> x, pair<long double,long double> y){
	long double a1=area(a,x,y),a2=area(b,x,y),a3=area(x,a,b),a4=area(y,a,b);
	if(online(a,x,y)||online(b,x,y)||online(x,a,b)||online(y,a,b)) return false;
	if((((a1<-eps)&&(a2>eps)) || ((a1>eps)&&(a2<-eps))) && ( ((a3<-eps)&&(a4>eps)) || ((a3>eps)&&(a4<-eps)))) return true;
	else return false;
}
bool eq(pair<long double,long double> a, pair<long double, long double> b){
	if(abs(a.first-b.first)<eps&&abs(a.second-b.second)<eps) return true;
	else return false;
}
bool touch(pair<long double,long double> a,pair<long double,long double> b,pair<long double,long double> x, pair<long double,long double> y){
	if(eq(a,b)&&eq(x,y)) return eq(a,x);
	else if(eq(a,b)){
		return online(a,x,y);
	}
	else if(eq(x,y)){
		return online(x,a,b);
	}
	long double a1=area(a,x,y),a2=area(b,x,y),a3=area(x,a,b),a4=area(y,a,b);
	if(online(a,x,y)||online(b,x,y)||online(x,a,b)||online(y,a,b)) return true;
	if((((a1<-eps)&&(a2>eps)) || ((a1>eps)&&(a2<-eps))) && ( ((a3<-eps)&&(a4>eps)) || ((a3>eps)&&(a4<-eps)))) return true;
	else return false;
}
vector<pair<pair<long double,long double>,pair<long double,long double> > > lns,bord;
vector<pair<int,long double> > adj[1000];
bool valid(pair<long double,long double> a,pair<long double,long double> b){
	for(auto i:bord){
		if(intersect(i.first,i.second,a,b)) return false;
	}
	return true;
}
int32_t main(){
	//ios::sync_with_stdio(0);
	//cin.tie(0);
	int n,s;
	cin >> n >> s;
	vector<int> bruh;
	for(int i=0; i<n; i++){
		long double a,b,c,d;
		cin >> a >> b >> c >> d;
		if(intersect({a,b},{c,d},{0,-300},{0,300})){
			pair<long double,long double> di ={c-a,d-b};
			long double t=(0-a)/di.first;
			pair<long double,long double> pt={a+t*di.first,b+t*di.second};
			lns.push_back({{a,b},pt});
			lns.push_back({pt,{c,d}});
			if(intersect({a,b},{c,d},{0,0},{0,300})){
				bruh.push_back(lns.size());
				lns.push_back({pt,pt});
			}
		}
		else lns.push_back({{a,b},{c,d}});
	}
	n=lns.size();
	bord.push_back({{s-eep,s-eep},{s-eep,-s+eep}});
	bord.push_back({{s-eep,-s+eep},{-s+eep,-s+eep}});
	bord.push_back({{-s+eep,-s+eep},{-s+eep,s-eep}});
	bord.push_back({{-s+eep,s-eep},{s-eep,s-eep}});
	lns.push_back({{s,s},{s,s}});
	lns.push_back({{s,-s},{s,-s}});
	lns.push_back({{-s,-s},{-s,-s}});
	lns.push_back({{-s,s},{-s,s}});
	for(int i=s; i<=200; i++){
		bruh.push_back(lns.size());
		lns.push_back({{0,i},{0,i}});
	}
	for(int i=0; i<(int)lns.size(); i++){
		for(int j=i+1; j<(int)lns.size(); j++){
			pair<long double,pair<pair<long double,long double>,pair<long double,long double> > > lol=lnln(lns[i].first,lns[i].second,lns[j].first,lns[j].second);
			if(valid(lol.second.first,lol.second.second)&&!touch(lol.second.first,lol.second.second,{0,0},{0,300})){
				adj[i].push_back({j,lol.first});
				adj[j].push_back({i,lol.first});
			}
		}
	}
	for(int i:bruh){
		for(int j=0; j<(int)lns.size(); j++){
			pair<long double,pair<pair<long double,long double>,pair<long double,long double> > > lol=lnln(lns[i].first,lns[i].second,lns[j].first,lns[j].second);
			if(valid(lol.second.first,lol.second.second)){
				if(lns[j].first.first<0-eps||lns[j].second.first<0-eps) adj[i].push_back({j,lol.first});
				else adj[j].push_back({i,lol.first});
			}
		}
	}
	priority_queue<pair<long double,int>,vector<pair<long double,int> >,greater<pair<long double,int> > > pq;
	long double loop[505][505],wtv[505][505];
	long double dist[505];
	int isbruh[505];
	memset(isbruh,0,sizeof(isbruh));
	for(int i:bruh){
		isbruh[i]=1;
	}
	//cout << lns[bruh[1]].second.first << ' ' << lns[bruh[1]].second.second << '\n';
	for(int i=0; i<(int)bruh.size(); i++){
		pq.push({0,bruh[i]});
		for(int j=0; j<505; j++) dist[j]=1e16;
		while(!pq.empty()){
			long double a=pq.top().first;
			int b=pq.top().second;
			pq.pop();
			if(a>dist[b]+eps) continue;
			//if(i==1){
			//	cout << lns[b].first.first << ' ' << lns[b].first.second << ' ' << lns[b].second.first << ' ' << lns[b].second.second << '\n';
			//	cout << a << '\n';
			//}
			for(auto j:adj[b]){
				assert(j.second>=-eps);
				if(isbruh[j.first]){
					if(lns[b].first.first>eps||lns[b].second.first>eps){
						if(dist[j.first]>a+j.second){
							dist[j.first]=a+j.second;
							//pq.push({a+j.second,j.first});
						}
					}
				}
				else{
					if(dist[j.first]>a+j.second){
						//if(i==1&&lns[j.first].first.first==-3&&lns[j.first].first.second==3&&lns[j.first].second.first==-3){
							//cout << j.first  << ' ' << b << '\n';
							//cout << lns[b].first.first << ' ' << lns[b].first.second << ' ' << a+j.second << '\n';
						//}
						dist[j.first]=a+j.second;
						pq.push({a+j.second,j.first});
					}
				}
			}
		}
		for(int j=0; j<(int)bruh.size(); j++){
			loop[i][j]=dist[bruh[j]];
		}
		//if(loop[i][i]==0) cout << i << "bruh\n";
	}
	
	for(int i=0; i<(int)lns.size(); i++) adj[i].clear();
	for(int i=0; i<(int)lns.size(); i++){
		for(int j=i+1; j<(int)lns.size(); j++){
			pair<long double,pair<pair<long double,long double>,pair<long double,long double> > > lol=lnln(lns[i].first,lns[i].second,lns[j].first,lns[j].second);
			if(valid(lol.second.first,lol.second.second)){
				adj[i].push_back({j,lol.first});
				adj[j].push_back({i,lol.first});
			}
		}
	}
	for(int i=0; i<(int)bruh.size(); i++){
		pq.push({0,bruh[i]});
		for(int j=0; j<505; j++) dist[j]=1e16;
		dist[bruh[i]]=0;
		while(!pq.empty()){
			long double a=pq.top().first;
			int b=pq.top().second;
			pq.pop();
			if(a>dist[b]+eps) continue;
			for(auto j:adj[b]){
				if(dist[j.first]>a+j.second){
					dist[j.first]=a+j.second;
					pq.push({a+j.second,j.first});
				}
			}
		}
		for(int j=0; j<(int)bruh.size(); j++){
			wtv[i][j]=dist[bruh[j]];
		}
	}
	long double ans=1e16;
	for(int i=0; i<(int)bruh.size(); i++){
		for(int j=0; j<(int)bruh.size(); j++) ans=min(ans,loop[i][j]+wtv[j][i]);
	}
	cout << fixed << setprecision(10) << ans;
}

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