Submission #698193

#	Time	Username	Problem	Language	Result	Execution time	Memory
698193		GusterGoose27	Fences (JOI18_fences)	C++17	0 / 100	1 ms	344 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-9;
ld dist[MAXN][MAXN];
int n, s;
pii r1(0, 0);
pii r2(1000,999);

int dot(pii a, pii b) {
	return a.first*b.first+a.second*b.second;
}

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

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

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

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

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

pii rot(pii a) { // 90* cc
	return pii(-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);
}

int operator*(pii a, pii b) {
	return a.first*b.second-a.second*b.first;
}

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

int sign(int a) {
	if (a > 0) return 1;
	if (a == 0) return 0;
	return -1;
}

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

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

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

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

bool intersect_single(pii a, pii b, pii c, pii 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(pii a, pii b, pii c, pii 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(pii(-s, -s));
	add(pii(s, -s));
	add(pii(s, s));
	add(pii(-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;
			pii p1 = points[lines[i].first], p2 = points[lines[i].second], p3 = points[j];
			pii 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;
				if (valid((pdd)p3, inter)) {
					curdist = abs(curdist*mag(p2-p1));
					bool rev = intersect_strict(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:142:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::map<std::pair<int, int>, int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  142 |   for (int j = 0; j < nodes.size(); j++) {
      |                   ~~^~~~~~~~~~~~~~

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