oj.uz

Submission #100466

# Submission time Handle Problem Language Result Execution time Memory
100466 2019-03-11T12:45:05 Z JPN20 Fences (JOI18_fences) C++17
51 / 100
 188 ms 484 KB 
#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.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 384 KB Output is correct
2 Correct 2 ms 256 KB Output is correct
3 Correct 3 ms 384 KB Output is correct
4 Correct 2 ms 384 KB Output is correct
5 Correct 2 ms 256 KB Output is correct
6 Correct 2 ms 256 KB Output is correct
7 Correct 2 ms 256 KB Output is correct
8 Correct 2 ms 384 KB Output is correct
9 Correct 3 ms 384 KB Output is correct
10 Correct 3 ms 484 KB Output is correct
11 Correct 2 ms 384 KB Output is correct
12 Correct 3 ms 256 KB Output is correct
13 Correct 4 ms 384 KB Output is correct
14 Correct 2 ms 256 KB Output is correct
15 Correct 2 ms 256 KB Output is correct
16 Correct 2 ms 384 KB Output is correct
17 Correct 3 ms 256 KB Output is correct
18 Correct 2 ms 384 KB Output is correct
19 Correct 3 ms 384 KB Output is correct
20 Correct 2 ms 256 KB Output is correct

Subtask #2
33.0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 384 KB Output is correct
2 Correct 2 ms 256 KB Output is correct
3 Correct 3 ms 384 KB Output is correct
4 Correct 2 ms 384 KB Output is correct
5 Correct 2 ms 256 KB Output is correct
6 Correct 2 ms 256 KB Output is correct
7 Correct 2 ms 256 KB Output is correct
8 Correct 2 ms 384 KB Output is correct
9 Correct 3 ms 384 KB Output is correct
10 Correct 3 ms 484 KB Output is correct
11 Correct 2 ms 384 KB Output is correct
12 Correct 3 ms 256 KB Output is correct
13 Correct 4 ms 384 KB Output is correct
14 Correct 2 ms 256 KB Output is correct
15 Correct 2 ms 256 KB Output is correct
16 Correct 2 ms 384 KB Output is correct
17 Correct 3 ms 256 KB Output is correct
18 Correct 2 ms 384 KB Output is correct
19 Correct 3 ms 384 KB Output is correct
20 Correct 2 ms 256 KB Output is correct
21 Correct 3 ms 256 KB Output is correct
22 Correct 53 ms 384 KB Output is correct
23 Correct 40 ms 384 KB Output is correct
24 Correct 39 ms 368 KB Output is correct
25 Correct 37 ms 384 KB Output is correct
26 Correct 46 ms 256 KB Output is correct
27 Correct 36 ms 384 KB Output is correct
28 Correct 46 ms 360 KB Output is correct
29 Correct 76 ms 376 KB Output is correct
30 Correct 85 ms 256 KB Output is correct
31 Correct 85 ms 368 KB Output is correct
32 Correct 64 ms 360 KB Output is correct
33 Correct 93 ms 476 KB Output is correct
34 Correct 68 ms 384 KB Output is correct
35 Correct 164 ms 376 KB Output is correct
36 Correct 188 ms 256 KB Output is correct
37 Correct 10 ms 256 KB Output is correct
38 Correct 3 ms 256 KB Output is correct
39 Correct 15 ms 256 KB Output is correct
40 Correct 2 ms 384 KB Output is correct
41 Correct 2 ms 384 KB Output is correct
42 Correct 3 ms 256 KB Output is correct
43 Correct 10 ms 256 KB Output is correct

Subtask #3
0 / 49.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 384 KB Output is correct
2 Correct 2 ms 256 KB Output is correct
3 Correct 3 ms 384 KB Output is correct
4 Correct 2 ms 384 KB Output is correct
5 Correct 2 ms 256 KB Output is correct
6 Correct 2 ms 256 KB Output is correct
7 Correct 2 ms 256 KB Output is correct
8 Correct 2 ms 384 KB Output is correct
9 Correct 3 ms 384 KB Output is correct
10 Correct 3 ms 484 KB Output is correct
11 Correct 2 ms 384 KB Output is correct
12 Correct 3 ms 256 KB Output is correct
13 Correct 4 ms 384 KB Output is correct
14 Correct 2 ms 256 KB Output is correct
15 Correct 2 ms 256 KB Output is correct
16 Correct 2 ms 384 KB Output is correct
17 Correct 3 ms 256 KB Output is correct
18 Correct 2 ms 384 KB Output is correct
19 Correct 3 ms 384 KB Output is correct
20 Correct 2 ms 256 KB Output is correct
21 Correct 3 ms 256 KB Output is correct
22 Correct 53 ms 384 KB Output is correct
23 Correct 40 ms 384 KB Output is correct
24 Correct 39 ms 368 KB Output is correct
25 Correct 37 ms 384 KB Output is correct
26 Correct 46 ms 256 KB Output is correct
27 Correct 36 ms 384 KB Output is correct
28 Correct 46 ms 360 KB Output is correct
29 Correct 76 ms 376 KB Output is correct
30 Correct 85 ms 256 KB Output is correct
31 Correct 85 ms 368 KB Output is correct
32 Correct 64 ms 360 KB Output is correct
33 Correct 93 ms 476 KB Output is correct
34 Correct 68 ms 384 KB Output is correct
35 Correct 164 ms 376 KB Output is correct
36 Correct 188 ms 256 KB Output is correct
37 Correct 10 ms 256 KB Output is correct
38 Correct 3 ms 256 KB Output is correct
39 Correct 15 ms 256 KB Output is correct
40 Correct 2 ms 384 KB Output is correct
41 Correct 2 ms 384 KB Output is correct
42 Correct 3 ms 256 KB Output is correct
43 Correct 10 ms 256 KB Output is correct
44 Incorrect 2 ms 256 KB Output isn't correct
45 Halted 0 ms 0 KB -