Submission #1224963

#	Time	Username	Problem	Language	Result	Execution time	Memory
1224963		PenguinsAreCute	Fences (JOI18_fences)	C++17	51 / 100	38 ms	1096 KiB

fences

#include <bits/stdc++.h>
using namespace std;
using ld = long double;
int main() {
	int n, s;
	cin >> n >> s;
	auto nearest = [](ld a, ld b, ld c, ld d, ld x, ld y) -> pair<ld,ld> {
		if(a == c)
			return {a, max(min(y, max(b, d)), min(b, d))};
		if(b == d)
			return {max(min(x, max(a, c)), min(a, c)), b};
		pair<ld,ld> ln1 = {(d-b)/ld(c-a), 0};
		ln1.second = b - ln1.first * a;
		pair<ld,ld> ln2 = {-1/ln1.first,0};
		ln2.second = y - ln2.first * x;
		pair<ld,ld> isect = {0,0};
		isect.first = (ln2.second - ln1.second) / (ln1.first - ln2.first);
		if(isect.first < a && isect.first < c)
			isect.first = min(a, c);
		if(isect.first > a && isect.first > c)
			isect.first = max(a, c);
		isect.second = ln1.first * isect.first + ln1.second;
		return isect;
	};
	auto dist = [](ld x1, ld y1, ld x2, ld y2) -> ld {return sqrt((x1-x2)*(x1-x2)+(y1-y2)*(y1-y2));};
	auto wind = [](ld x1, ld y1, ld x2, ld y2) -> bool {
		if((x1>=0) == (x2>=0))
			return 0;
		ld m = (y2-y1)/(x2-x1);
		ld c = y1-x1*m;
		return (c > 0);
	};
	auto valid = [s](ld x1, ld y1, ld x2, ld y2) -> bool {
		ld m = (y2 - y1) / (x2 - x1);
		ld c = y1 - m * x1;
		ld xl = max(min(x1, x2), ld(-s)), xr = min(max(x1, x2), ld(s));
		if(x1 == x2 || (y1 == y2 && abs(y1) < s - 1e-7))
			return (xr <= xl + 1e-7);
		if(y1 == y2)
			return 1;
		ld yn = -s, yp = s;
		yn = (yn - c) / m;
		yp = (yp - c) / m;
		if(yn > yp)
			swap(yn, yp);
		xl = max(xl, yn);
		xr = min(xr, yp);
		return xr <= xl + 1e-7;
	};
	ld a[n+4], b[n+4], c[n+4], d[n+4];
	for(int i=0;i<n;i++)
		cin >> a[i] >> b[i] >> c[i] >> d[i];
	a[n] = b[n] = b[n+1] = a[n+3] = s;
	a[n+1] = a[n+2] = b[n+2] = b[n+3] = -s;
	for(int i=n;i<n+4;i++)
		c[i] = a[i], d[i] = b[i];
	n += 4;
	vector<vector<ld>> adj(2*n,vector<ld>(2*n,1e9));
	for(int i=0;i<2*n;i++)
		adj[i][i]=0;
	for(int i=0;i<n;i++)
		for(int j=i+1;j<n;j++) {
			if(auto [x, y] = nearest(a[j], b[j], c[j], d[j], a[i], b[i]); valid(x,y,a[i],b[i])) {
				bool wnd = wind(a[j],b[j],x,y)^wind(x,y,a[i],b[i])^wind(a[i],b[i],a[i],b[i]);
				ld cur = dist(x,y,a[i],b[i]);
				adj[2*i][2*j^wnd] = min(adj[2*i][2*j^wnd], cur);
				adj[2*i^1][2*j^1^wnd] = min(adj[2*i^1][2*j^1^wnd], cur);
				adj[2*j^wnd][2*i] = min(adj[2*j^wnd][2*i], cur);
				adj[2*j^1^wnd][2*i^1] = min(adj[2*j^1^wnd][2*i^1], cur);
			}
			if(auto [x, y] = nearest(a[j], b[j], c[j], d[j], c[i], d[i]); valid(x,y,c[i],d[i])) {
				bool wnd = wind(a[j],b[j],x,y)^wind(x,y,c[i],d[i])^wind(c[i],d[i],a[i],b[i]);
				ld cur = dist(x,y,c[i],d[i]);
				adj[2*i][2*j^wnd] = min(adj[2*i][2*j^wnd], cur);
				adj[2*i^1][2*j^1^wnd] = min(adj[2*i^1][2*j^1^wnd], cur);
				adj[2*j^wnd][2*i] = min(adj[2*j^wnd][2*i], cur);
				adj[2*j^1^wnd][2*i^1] = min(adj[2*j^1^wnd][2*i^1], cur);
			}
			if(auto [x, y] = nearest(a[i], b[i], c[i], d[i], a[j], b[j]); valid(x,y,a[j],b[j])) {
				bool wnd = wind(a[i],b[i],x,y)^wind(x,y,a[j],b[j])^wind(a[j],b[j],a[j],b[j]);
				ld cur = dist(x,y,a[j],b[j]);
				adj[2*i][2*j^wnd] = min(adj[2*i][2*j^wnd], cur);
				adj[2*i^1][2*j^1^wnd] = min(adj[2*i^1][2*j^1^wnd], cur);
				adj[2*j^wnd][2*i] = min(adj[2*j^wnd][2*i], cur);
				adj[2*j^1^wnd][2*i^1] = min(adj[2*j^1^wnd][2*i^1], cur);
			}
			if(auto [x, y] = nearest(a[i], b[i], c[i], d[i], c[j], d[j]); valid(x,y,c[j],d[j])) {
				bool wnd = wind(a[i],b[i],x,y)^wind(x,y,c[j],d[j])^wind(c[j],d[j],a[j],b[j]);
				ld cur = dist(x,y,c[j],d[j]);
				adj[2*i][2*j^wnd] = min(adj[2*i][2*j^wnd], cur);
				adj[2*i^1][2*j^1^wnd] = min(adj[2*i^1][2*j^1^wnd], cur);
				adj[2*j^wnd][2*i] = min(adj[2*j^wnd][2*i], cur);
				adj[2*j^1^wnd][2*i^1] = min(adj[2*j^1^wnd][2*i^1], cur);
			}
		}
	for(int k=0;k<2*n;k++)
		for(int i=0;i<2*n;i++)
			for(int j=0;j<2*n;j++)
				adj[i][j]=min(adj[i][j],adj[i][k]+adj[k][j]);
	ld ans = 1e9;
	for(int i=0;i<2*n;i++)
		ans = min(ans, adj[i][i^1]);
	cout << fixed << setprecision(15) << ans;
}

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