Submission #698226

#	Time	Username	Problem	Language	Result	Execution time	Memory
698226		GusterGoose27	Fences (JOI18_fences)	C++17	0 / 100	1 ms	388 KiB

fences

#include <bits/stdc++.h>

using namespace std;

typedef long double ld;
typedef pair<int, int> pii;
typedef pair<ld, ld> pdd;

const int MAXN = 408;
const ld inf = 1e6;
const ld eps = 1e-6;
ld dist[MAXN][MAXN];
int n, s;
pdd r1(0, 0);
pdd r2(10001,9999);

ld dot(pdd a, pdd b) {
	return a.first*b.first+a.second*b.second;
}

pdd operator*(ld v, pdd a) {
	return pdd(a.first*v, a.second*v);
}

ld mag(pdd a) {
	return sqrt(a.first*a.first+a.second*a.second);
}

pdd rot(pdd a) { // 90* cc
	return pdd(-a.second, a.first);
}

pdd operator-(pdd a, pdd b) {
	return pdd(a.first-b.first, a.second-b.second);
}

pdd operator+(pdd a, pdd b) {
	return pdd(a.first+b.first, a.second+b.second);
}

ld operator*(pdd a, pdd b) {
	return a.first*b.second-a.second*b.first;
}

int sign(ld a) {
	if (a > eps) return 1;
	if (a < eps) return -1;
	return 0;
}

map<pdd, int> nodes;
pdd points[MAXN];

int hsh(int i, bool b) {
	return 2*i+b;
}

void add(pdd p) {
	if (nodes.find(p) == nodes.end()) {
		int a = nodes.size();
		nodes[p] = a;
		points[a] = p;
	}
}

bool intersect_single(pdd a, pdd b, pdd c, pdd d) {
	return sign((c-a)*(b-a))*sign((d-a)*(b-a)) <= 0;
}

bool single_strict(pdd a, pdd b, pdd c, pdd d) {
	return ((c-a)*(b-a))*((d-a)*(b-a)) < -eps;
}

bool intersect(pdd a, pdd b, pdd c, pdd d) {
	return intersect_single(a, b, c, d) && intersect_single(c, d, a, b);
}

bool intersect_strict(pdd a, pdd b, pdd c, pdd d) {
	return single_strict(a, b, c, d) && single_strict(c, d, a, b);
}

bool contained(pdd a) {
	return (-s+eps < a.first && a.first < s-eps && -s+eps < a.second && a.second < s-eps);
}

bool valid(pdd a, pdd b) {
	if (contained(0.5*(a+b))) return 0;
	for (int i = 0; i < 4; i++) {
		if (intersect_strict((pdd)points[i], (pdd)points[(i+1)%4], a, b)) return 0;
	}
	return 1;
}

int main() {
	ios_base::sync_with_stdio(false); cin.tie(NULL);
	cin >> n >> s;
	int m = 4*n+8;
	add(pdd(-s, -s));
	add(pdd(s, -s));
	add(pdd(s, s));
	add(pdd(-s, s));
	for (int i = 0; i < m; i++) {
		fill(dist[i], dist[i]+m, inf);
	}
	vector<pii> lines;
	for (int i = 0; i < n; i++) {
		pii p1, p2;
		cin >> p1.first >> p1.second >> p2.first >> p2.second;
		add(p1); add(p2);
		int a = nodes[p1], b = nodes[p2];
		lines.push_back(pii(a, b));
		bool rev = intersect(r1, r2, p1, p2);
		dist[2*a][2*b^rev] = 0;
		dist[2*b^rev][2*a] = 0;
		dist[2*a+1][2*b^1^rev] = 0;
		dist[2*b^1^rev][2*a+1] = 0;
	}
	m = 2*nodes.size();
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < nodes.size(); j++) {
			if (lines[i].first == j || lines[i].second == j) continue;
			pdd p1 = points[lines[i].first], p2 = points[lines[i].second], p3 = points[j];
			pdd p4 = p3+rot(p2-p1);
			if (intersect_single(p3, p4, p1, p2)) {
				ld curdist = (ld)((p3-p1)*(p2-p1))/dot(p2-p1, p2-p1); // this is actually dist/mag(p2-p1)
				pdd inter = curdist*rot(p2-p1)+(pdd)p3;
				assert(abs(mag(p2-inter)+mag(p1-inter)-mag(p2-p1)) < eps);
				if (valid((pdd)p3, inter)) {
					curdist = abs(curdist*mag(p2-p1));
					bool rev = intersect(r1, r2, p3, p1);
					dist[2*j][2*lines[i].first^rev] = dist[2*lines[i].first^rev][2*j] = min(curdist, dist[2*j][2*lines[i].first^rev]);
					dist[2*j^1][2*lines[i].first^1^rev] = dist[2*lines[i].first^1^rev][2*j^1] = min(curdist, dist[2*j^1][2*lines[i].first^1^rev]);
				}
			}
		}
	}
	for (int i = 0; i < m/2; i++) {
		dist[2*i][2*i] = dist[2*i+1][2*i+1] = 0;
		for (int j = i+1; j < m/2; j++) {
			if (valid((pdd)points[i], (pdd)points[j])) {
				ld curdist = mag(points[j]-points[i]);
				bool rev = intersect(points[i], points[j], r1, r2);
				dist[2*i][2*j^rev] = dist[2*j^rev][2*i] = min(dist[2*i][2*j^rev], curdist);
				dist[2*i^1][2*j^1^rev] = dist[2*j^1^rev][2*i^1] = min(dist[2*i^1][2*j^1^rev], curdist);
			}
		}
	}
	for (int i = 0; i < m; i++) {
		for (int j = 0; j < m; j++) {
			for (int k = 0; k < m; k++) {
				dist[j][k] = min(dist[j][k], dist[j][i]+dist[i][k]);
			}
		}
	}
	ld ans = inf;
	for (int i = 0; i < m/2; i++) {
		ans = min(ans, dist[2*i][2*i+1]);
	}
	// for (int i = 0; i < m/2; i++) {
	// 	if (abs(ans-dist[2*i][2*i+1]) < eps) cout << points[i].first << " " << points[i].second << "\n";
	// }
	cout << fixed << setprecision(10) << ans << "\n";
}

Compilation message (stderr)

fences.cpp: In function 'int main()':
fences.cpp:120:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::map<std::pair<long double, long double>, int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  120 |   for (int j = 0; j < nodes.size(); j++) {
      |                   ~~^~~~~~~~~~~~~~

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