Submission #529467

#	Time	Username	Problem	Language	Result	Execution time	Memory
529467		8e7	Fences (JOI18_fences)	C++17	100 / 100	63 ms	1732 KiB

fences

//Challenge: Accepted
#include <bits/stdc++.h>
using namespace std;
#ifdef zisk
void debug(){cout << endl;}
template<class T, class ... U> void debug(T a, U ...b ){cout << a << " ", debug(b...);}
template<class T> void pary(T l, T r) {
	while (l != r) cout << *l << " ", l++;
	cout << endl;
}
#else
#define debug(...) 0
#define pary(...) 0
#endif
#define ll long long
#define maxn 420
#define pii pair<double, double>
#define eps 1e-9
#define x first
#define y second
#define io ios_base::sync_with_stdio(0);cin.tie(0);

pii vec(pii p, pii q) {return {q.x - p.x, q.y - p.y};}
pii operator *(pii p, double x) {return {p.x * x, p.y * x};}
pii operator +(pii p, pii q){return {p.x + q.x, p.y + q.y};}
double dot(pii p, pii q){return p.x * q.x + p.y * q.y;}
double cross(pii p, pii q){return p.x * q.y - p.y * q.x;}
int sgn(double x){return (x > eps ? 1 : (x > -eps ? 0 : -1));}
bool inl(pii p, pii l1, pii l2) {
	return abs(cross(vec(p, l1), vec(p, l2))) <= eps && dot(vec(p, l1), vec(p, l2)) <= eps;
}
bool inter(pii p1, pii p2, pii q1, pii q2) {
	if (inl(p1, q1, q2) || inl(p2, q1, q2) || inl(q1, p1, p2) || inl(q2, p1, p2)) return 1;
	if (sgn(cross(vec(p1, q1), vec(p1, q2))) != sgn(cross(vec(p2, q1), vec(p2, q2))) &&
sgn(cross(vec(q1, p1), vec(q1, p2))) != sgn(cross(vec(q2, p1), vec(q2, p2)))) return 1;
	return 0;
}
double sd(pii p, pii q){return (q.x - p.x) * (q.x - p.x) + (q.y - p.y) * (q.y - p.y);}

pii getpnt(pii p, pii l1, pii l2) {
	pii vi = vec(l1, l2);
	if (sgn(dot(vi, vec(l1, p))) * sgn(dot(vi, vec(l2, p))) != 1) {
		double len = dot(vec(l1, p), vi) / sd(l1, l2);
		return l1 + (vi*len);
	} else {
		if (sd(p, l1) < sd(p, l2)) return l1;
		else return l2;
	}
}
double dis(pii p, pii l1, pii l2) {
	return sqrt(sd(p, getpnt(p, l1, l2)));	
}

pii edge[4];
bool valid(pii p, pii q) {
	bool op[4], oq[4];
	int pc = 0, qc = 0;
	for (int i = 0;i < 4;i++) {
		op[i] = inl(p, edge[i], edge[(i+1)%4]);
		oq[i] = inl(q, edge[i], edge[(i+1)%4]);
		pc += op[i] ? 1 : 0, qc += oq[i] ? 1 : 0;
	}

	if (pc && qc) {
		for (int i = 0;i < 4;i++) {
			if (op[i] && oq[i]) return 1;
		}
		return 0;
	} else {
		for (int i = 0;i < 4;i++) {
			if (inter(p, q, edge[i], edge[(i+1)%4])) {
				if (!op[i] && !oq[i]) return 0;
			}
		}
		return 1;
	}	
}

const pii ray0 = {0, 0}, ray1 = {maxn, 1};
pii a[maxn];

const double inf = 1e9;
double g[maxn][maxn];
int main() {
	io
	int n, s;
	cin >> n >> s;
	for (int i = 0;i < n;i++) {
		cin >> a[2*i].x >> a[2*i].y >> a[2*i+1].x >> a[2*i+1].y;
	}	
	edge[0] = {s, s}, edge[1] = {s, -s}, edge[2] = {-s, -s}, edge[3] = {-s, s};
	
	int m = 4 * n + 8;
	for (int i = 0;i < m;i++) {
		for (int j = 0;j < m;j++) g[i][j] = inf;
		g[i][i] = 0;
	}

	
	double ans = 8 * s;
	auto chmin = [&](double &x, double d){x = min(x, d);};
	auto addedge = [&](int i, int j, double d, bool type) {
		if (type) {
			chmin(g[i*2][j*2+1], d);
			chmin(g[j*2+1][i*2], d);
			chmin(g[i*2+1][j*2], d);
			chmin(g[j*2][i*2+1], d);
		} else {
			chmin(g[i*2][j*2], d);
			chmin(g[j*2][i*2], d);
			chmin(g[i*2+1][j*2+1], d);
			chmin(g[j*2+1][i*2+1], d);
		}
	};
	auto change = [&](pii p, pii q) {return inter(p, q, ray0, ray1);};
	for (int i = 0;i < 2 * n;i++) {
		for (int j = 0;j < 2 * n;j+=2) {
			if (i == j) continue;
			if (i % 2 == 0 && j == i+1) {
				addedge(i, j, 0, change(a[i], a[j]));	
			} else {
				pii best;
				if (j % 2) best = getpnt(a[i], a[j], a[j-1]);
				else best = getpnt(a[i], a[j], a[j+1]);
				if (valid(a[i], best)) {
					addedge(i, j, sqrt(sd(best, a[i])), change(a[i], best) ^ change(best, a[j]));
				}
			}
		}
		if (i % 2 == 0) {
			for (int j = 0;j < 4;j++) {
				pii best = getpnt(edge[j], a[i], a[i+1]);		
				if (valid(edge[j], best)) {
					addedge(2*n+j, i, sqrt(sd(edge[j], best)), change(edge[j], best) ^ change(best, a[i]));
				}
			}	
		}
	}	
	for (int i = 0;i < 4;i++) {
		addedge(2*n+i, 2*n+(i+1)%4, 2*s, change(edge[i], edge[(i+1)%4]));
	}
	for (int k = 0;k < m;k++) {
		for (int i = 0;i < m;i++) {
			for (int j = 0;j < m;j++) {
				g[i][j] = min(g[i][j], g[i][k] + g[k][j]);
			}
		}
	}	
	for (int i = 0;i < m;i+=2) {
		ans = min(ans, g[i][i+1]);
	}
	cout << fixed << setprecision(10) << ans << endl;
}

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