Submission #100466

#	Time	Username	Problem	Language	Result	Execution time	Memory
100466		JPN20	Fences (JOI18_fences)	C++17	51 / 100	188 ms	484 KiB

fences

#include <bits/stdc++.h>
using namespace std;

struct Point { double px, py; };
struct Segment { Point p1, p2; };
double dst(Point a1, Point a2) { return sqrtl((a1.px - a2.px) * (a1.px - a2.px) + (a1.py - a2.py) * (a1.py - a2.py)); } 
double crs(Point a1, Point a2) { return a1.px * a2.px + a1.py * a2.py; }
double dot(Point a1, Point a2) { return a1.px * a2.py - a1.py * a2.px; }

int ccw(Point a1, Point a2, Point a3) {
	Point a4 = Point{a2.px - a1.px, a2.py - a1.py};
	Point a5 = Point{a3.px - a2.px, a3.py - a2.py};
	double I = dot(a4, a5);
	if (I < -1e-8) return -1;
	if (I > 1e-8) return 1;
	return 0;
}

bool its(Segment a1, Segment a2) {
	int cnt1 = 0;
	if (ccw(a1.p1, a1.p2, a2.p1) * ccw(a1.p1, a1.p2, a2.p2) == -1) cnt1++;
	if (ccw(a2.p1, a2.p2, a1.p1) * ccw(a2.p1, a2.p2, a1.p2) == -1) cnt1++;
	if (cnt1 == 2) return true;
	return false;
}

Point projection(Point a1, Segment a2) {
	if (dst(a2.p1, a2.p2) < 1e-5) return a2.p1;
	
	long double DD = fabs(dot(Point{a2.p2.px - a2.p1.px, a2.p2.py - a2.p1.py}, Point{a1.px - a2.p1.px, a1.py - a2.p1.py})) / dst(a2.p1, a2.p2);
	Point V = Point{a2.p2.py - a2.p1.py, a2.p2.px - a2.p1.px};
	V.px /= dst(a2.p1, a2.p2) / DD;
	V.py /= dst(a2.p1, a2.p2) / DD;
	
	Point W1 = Point{a1.px + 2.0 * V.px, a1.py - 2.0 * V.py};
	if (its(Segment{a1, W1}, a2) == true) return Point{a1.px + V.px, a1.py - V.py};
	return Point{a1.px - V.px, a1.py + V.py};
}

pair<Point, Point> dst1(Point a1, Point a2) {
	return make_pair(a1, a2);
}
pair<Point, Point> dst2(Point a1, Segment a2) {
	long double V1 = dst(a1, a2.p1);
	long double V2 = dst(a1, a2.p2);
	long double V3 = fabs(dot(Point{a2.p2.px - a2.p1.px, a2.p2.py - a2.p1.py}, Point{a1.px - a2.p1.px, a1.py - a2.p1.py})) / dst(a2.p1, a2.p2);
	if (crs(Point{a2.p2.px - a2.p1.px, a2.p2.py - a2.p1.py}, Point{a1.px - a2.p1.px, a1.py - a2.p1.py}) < 0) V3 = 1e9;
	if (crs(Point{a2.p1.px - a2.p2.px, a2.p1.py - a2.p2.py}, Point{a1.px - a2.p2.px, a1.py - a2.p2.py}) < 0) V3 = 1e9;
	
	if (V1 <= V2 && V1 <= V3) return make_pair(a1, a2.p1);
	if (V2 <= V1 && V2 <= V3) return make_pair(a1, a2.p2);
	return make_pair(a1, projection(a1, a2));
}
pair<Point, Point> dst3(Segment a1, Point a2) {
	pair<Point, Point> D = dst2(a2, a1);
	return make_pair(D.second, D.first);
}
pair<Point, Point> dst4(Segment a1, Segment a2) {
	pair<Point, Point> D1 = dst2(a1.p1, a2); long double V1 = dst(D1.first, D1.second);
	pair<Point, Point> D2 = dst2(a1.p2, a2); long double V2 = dst(D2.first, D2.second);
	pair<Point, Point> D3 = dst3(a1, a2.p1); long double V3 = dst(D3.first, D3.second);
	pair<Point, Point> D4 = dst3(a1, a2.p2); long double V4 = dst(D4.first, D4.second);
	
	if (V1 <= V2 && V1 <= V3 && V1 <= V4) return D1;
	if (V2 <= V1 && V2 <= V3 && V2 <= V4) return D2;
	if (V3 <= V1 && V3 <= V2 && V3 <= V4) return D3;
	return D4;
}

int N; double S; Segment L[10];
pair<Point, Point> G[10][10]; bool used[10][10];

long double CONSTANT = 0.1145141919810893;

int main() {
	cin >> N >> S;
	for (int i = 4; i < 4 + N; i++) cin >> L[i].p1.px >> L[i].p1.py >> L[i].p2.px >> L[i].p2.py;
	L[0].p1.px = -S; L[0].p1.py = -S; L[0].p2 = L[0].p1;
	L[1].p1.px = -S; L[1].p1.py = +S; L[1].p2 = L[1].p1;
	L[2].p1.px = +S; L[2].p1.py = +S; L[2].p2 = L[2].p1;
	L[3].p1.px = +S; L[3].p1.py = -S; L[3].p2 = L[3].p1;
	
	for (int i = 0; i < 4 + N; i++) {
		for (int j = 0; j < 4 + N; j++) {
			if (i == j) continue;
			G[i][j] = dst4(L[i], L[j]); used[i][j] = true;
			
			vector<int> E1 = {0, 1, 2, 3, 0, 1};
			vector<int> E2 = {1, 2, 3, 0, 2, 3};
			for (int k = 0; k < 6; k++) {
				if (its(Segment{G[i][j].first, G[i][j].second}, Segment{L[E1[k]].p1, L[E2[k]].p1}) == true) used[i][j] = false;
			}
		}
	}
	
	long double ans = 1e9;
	
	for (int i = 1; i < (1 << (4 + N)); i++) {
		vector<int> vec;
		for (int j = 0; j < 4 + N; j++) { if ((i / (1 << j)) % 2 == 1) vec.push_back(j); }
		int s = vec[0];
		
		do {
			if (vec[0] != s) break;
			
			bool ok = true;
			for (int j = 0; j < (int)vec.size(); j++) {
				int s1 = vec[j], s2 = vec[(j + 1) % vec.size()];
				if (used[s1][s2] == false) { ok = false; break; }
			}
			
			if (ok == false) continue;
			
			vector<Point>tup;
			for (int j = 0; j < (int)vec.size(); j++) {
				int s1 = vec[j], s2 = vec[(j + 1) % vec.size()];
				tup.push_back(G[s1][s2].first);
				tup.push_back(G[s1][s2].second);
			}
			
			long double D = 0; int cnt1 = 0;
			for (int j = 0; j < (int)tup.size(); j++) {
				Point s1 = tup[j], s2 = tup[(j + 1) % tup.size()];
				if (s1.px < CONSTANT && CONSTANT < s2.px) {
					long double Y = (CONSTANT - s1.px) * s2.py + (s2.px - CONSTANT) * s1.py;
					Y /= (s2.px - s1.px);
					if (Y > 0) cnt1++;
				}
				if (s2.px < CONSTANT && CONSTANT < s1.px && s1.py > 0) {
					long double Y = (CONSTANT - s2.px) * s1.py + (s1.px - CONSTANT) * s2.py;
					Y /= (s1.px - s2.px);
					if (Y > 0) cnt1--;
				}
				if (j % 2 == 0) D += dst(s1, s2);
			}
			
			if (cnt1 == 1) ans = min(ans, D);
			
		}while(next_permutation(vec.begin(), vec.end()));
	}
	printf("%.12Lf\n", ans);
	return 0;
}

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