QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#103463#3184. Around the TrackPetroTarnavskyiAC ✓4ms3848kbC++174.7kb2023-05-05 22:12:012023-05-05 22:12:01

Judging History

你现在查看的是最新测评结果

  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2023-05-05 22:12:01]
  • 评测
  • 测评结果:AC
  • 用时:4ms
  • 内存:3848kb
  • [2023-05-05 22:12:01]
  • 提交

answer

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

#define SZ(a) (int)a.size()
#define ALL(a) a.begin(), a.end()
#define FOR(i, a, b) for (int i = (a); i<(b); ++i)
#define RFOR(i, b, a) for (int i = (b)-1; i>=(a); --i)
#define MP make_pair
#define PB push_back
#define F first
#define S second

typedef long long LL;
typedef pair<int, int> PII;
typedef vector<int> VI;

const int N = 107;
const double INF = 1e47;

struct Point {
	int x, y;
	Point() {}
	Point(int _x, int _y): x(_x), y(_y) {}
	Point operator-(const Point& p) const {
		return Point(x - p.x, y - p.y);
	}
	int operator*(const Point& p) const {
		return x * p.y - p.x * y;
	}
	bool operator<(const Point& p) const {
		return x != p.x ? x < p.x : y < p.y;
	}
	bool operator==(const Point& p) const {
		return x == p.x && y == p.y;
	}
	int dot(const Point& p) const {
		return x * p.x + y * p.y;
	}
	int d2() const {
		return x * x + y * y;
	}
	double len() const {
		return sqrt(d2());
	}
};

int sign(int x) {
	if (x == 0) {
		return 0;
	}
	return x > 0 ? 1 : -1;
}

bool intersect(const Point& a, const Point& b, const Point& c, const Point& d) {
	return sign((b - a) * (c - a)) * sign((b - a) * (d - a)) <= 0 &&
		sign((d - c) * (a - c)) * sign((d - c) * (b - c)) < 0;
}

bool belongs(const Point& a, const Point& b, const Point& c) {
	return (b - a) * (c - a) == 0 && (b - a).dot(c - a) >= 0 && (a - b).dot(c - b) >= 0;
}

int area(const vector<Point>& p) {
	int res = 0;
	FOR(i, 0, SZ(p) - 1) {
		res += (p[i + 1] - p[0]) * (p[i] - p[0]);
	}
	return abs(res);
}

bool segmentInside(const vector<Point>& p, const Point& a, const Point& b, bool needStrictly) {
	int i = find(ALL(p), a) - p.begin(), j = find(ALL(p), b) - p.begin();
	if (((i + 1) % SZ(p) == j || (j + 1) % SZ(p) == i) && needStrictly) {
		return false;
	}
	vector<Point> ij, ji;
	for (int k = i; ; k = (k + 1) % SZ(p)) {
		ij.push_back(p[k]);
		if (k == j) {
			break;
		}
	}
	for (int k = j; ; k = (k + 1) % SZ(p)) {
		ji.push_back(p[k]);
		if (k == i) {
			break;
		}
	}
	return area(ij) + area(ji) == area(p);
}

double dist[N][N];

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout << fixed << setprecision(10);
	vector<Point> p[2];
	FOR(i, 0, 2) {
		int n;
		cin >> n;
		p[i].resize(n);
		for (Point& pij : p[i]) {
			cin >> pij.x >> pij.y;
		}
	}
	int iMinPoint[2] = {0, 0};
	FOR(j, 0, 2) {
		FOR(i, 0, SZ(p[j])) {
			if (p[j][i] < p[j][iMinPoint[j]]) {
				iMinPoint[j] = i;
			}
		}
	}
	vector<int> U, D;
	vector<int> idxes(SZ(p[0]));
	iota(ALL(idxes), 0);
	sort(ALL(idxes), [&](int i, int j) {return p[0][i] < p[0][j];});
	for (int j : idxes) {
		while (SZ(U) > 1 && (p[0][U.back()] - p[0][U[SZ(U) - 2]]) * (p[0][j] - p[0][U[SZ(U) - 2]]) >= 0) {
			U.pop_back();
		}
		while (SZ(D) > 1 && (p[0][D.back()] - p[0][D[SZ(D) - 2]]) * (p[0][j] - p[0][D[SZ(D) - 2]]) <= 0) {
			D.pop_back();
		}
		U.push_back(j);
		D.push_back(j);
	}
	vector<int> convex = D;
	RFOR(j, SZ(U) - 1, 0) {
		convex.push_back(U[j]);
	}
	assert(convex[0] == iMinPoint[0] && convex.back() == iMinPoint[0]);
	double ans = 0;
	FOR(i, 0, SZ(convex) - 1) {
		const Point& a = p[0][convex[i]], b = p[0][convex[i + 1]];
		vector<Point> points;
		for (int j = convex[i]; ; j = (j + 1) % SZ(p[0])) {
			points.push_back(p[0][j]);
			if (j == convex[i + 1]) {
				break;
			}
		}
		int s = 0, t = SZ(points) - 1;
		bool inside = false;
		FOR(j, iMinPoint[1], iMinPoint[1] + SZ(p[1])) {
			const Point& c = p[1][j % SZ(p[1])], d = p[1][(j + 1) % SZ(p[1])];
			if (belongs(a, b, c)) {
				inside = (b - a) * (d - a) > 0;
			}
			else {
				inside ^= intersect(a, b, c, d);
			}
			if (inside || belongs(a, b, d)) {
				points.push_back(d);
			}
		}
		int m = SZ(points);
		FOR(j, 0, m) {
			dist[j][j] = 0;
			FOR(k, j + 1, m) {
				dist[j][k] = dist[k][j] = INF;
				double len = (points[k] - points[j]).len();
				bool can = true;
				const Point& c = points[j], d = points[k];
				FOR(it, 0, 2) {
					FOR(l, 0, SZ(p[it])) {
						const Point& e = p[it][l], f = p[it][(l + 1) % SZ(p[it])];
						if ((d - c) * (f - e) == 0) {
							continue;
						}
						can &= !intersect(c, d, e, f);
					}
				}
				if (!can) {
					continue;
				}
				if ((j <= t) ^ (k <= t)) {
					dist[j][k] = dist[k][j] = len;
					continue;
				}
				if (j <= t) {
					can &= !segmentInside(p[0], c, d, true);
				}
				else {
					can &= segmentInside(p[1], c, d, false);
				}
				if (can) {
					dist[j][k] = dist[k][j] = len;
				}
			}
		}
		FOR(l, 0, m) {
			FOR(j, 0, m) {
				FOR(k, 0, m) {
					dist[j][k] = min(dist[j][k], dist[j][l] + dist[k][l]);
				}
			}
		}
		ans += dist[s][t];
	}
	cout << ans << "\n";
	return 0;
}

详细

Test #1:

score: 100
Accepted
time: 2ms
memory: 3788kb

input:

3
1 1
2 1
1 2
3
0 0
4 0
0 4

output:

3.4142135624

result:

ok found '3.4142136', expected '3.4142136', error '0.0000000'

Test #2:

score: 0
Accepted
time: 2ms
memory: 3640kb

input:

5
1 1
5 1
5 5
3 3
1 5
4
0 0
6 0
6 6
0 6

output:

16.0000000000

result:

ok found '16.0000000', expected '16.0000000', error '0.0000000'

Test #3:

score: 0
Accepted
time: 0ms
memory: 3628kb

input:

5
1 1
5 1
5 5
3 3
1 5
5
0 0
6 0
6 6
3 4
0 6

output:

16.4721359550

result:

ok found '16.4721360', expected '16.4721360', error '0.0000000'

Test #4:

score: 0
Accepted
time: 1ms
memory: 3648kb

input:

5
2 2
6 2
6 6
4 4
2 6
4
0 0
8 0
8 8
0 8

output:

16.0000000000

result:

ok found '16.0000000', expected '16.0000000', error '0.0000000'

Test #5:

score: 0
Accepted
time: 2ms
memory: 3644kb

input:

5
2 2
6 2
6 6
4 4
2 6
5
0 0
8 0
8 8
4 5
0 8

output:

16.4721359550

result:

ok found '16.4721360', expected '16.4721360', error '0.0000000'

Test #6:

score: 0
Accepted
time: 2ms
memory: 3644kb

input:

12
1 1
1 4
-1 4
-1 1
-4 1
-4 -1
-1 -1
-1 -4
1 -4
1 -1
4 -1
4 1
12
2 2
2 5
-2 5
-2 2
-5 2
-5 -2
-2 -2
-2 -5
2 -5
2 -2
5 -2
5 2

output:

25.8885438200

result:

ok found '25.8885438', expected '25.8885438', error '0.0000000'

Test #7:

score: 0
Accepted
time: 2ms
memory: 3656kb

input:

8
1 1
15 1
15 7
14 7
14 2
2 2
2 7
1 7
15
0 0
16 0
16 8
13 8
12 4
11 6
10 3
9 6
8 5
7 6
6 3
5 6
4 4
3 8
0 8

output:

43.6832385059

result:

ok found '43.6832385', expected '43.6832385', error '0.0000000'

Test #8:

score: 0
Accepted
time: 0ms
memory: 3696kb

input:

8
1 1
15 1
15 7
14 7
14 2
2 2
2 7
1 7
15
0 0
16 0
16 8
13 8
12 4
11 8
10 3
9 8
8 5
7 8
6 3
5 8
4 4
3 8
0 8

output:

43.6832385059

result:

ok found '43.6832385', expected '43.6832385', error '0.0000000'

Test #9:

score: 0
Accepted
time: 1ms
memory: 3636kb

input:

8
1 1
15 1
15 7
14 7
14 2
2 2
2 7
1 7
15
0 0
16 0
16 8
13 8
12 4
11 7
10 3
9 7
8 5
7 7
6 3
5 7
4 4
3 8
0 8

output:

43.6832385059

result:

ok found '43.6832385', expected '43.6832385', error '0.0000000'

Test #10:

score: 0
Accepted
time: 1ms
memory: 3704kb

input:

12
1 1
10 1
10 6
9 6
9 2
6 2
6 4
5 4
5 2
2 2
2 6
1 6
12
0 0
11 0
11 7
8 7
8 3
7 3
7 5
4 5
4 3
3 3
3 7
0 7

output:

33.1529824451

result:

ok found '33.1529824', expected '33.1529824', error '0.0000000'

Test #11:

score: 0
Accepted
time: 1ms
memory: 3628kb

input:

7
1 1
5 1
5 19
4 2
3 18
2 2
1 19
9
0 0
6 0
6 20
5 20
4 3
3 19
2 3
1 20
0 20

output:

102.1290318405

result:

ok found '102.1290318', expected '102.1290318', error '0.0000000'

Test #12:

score: 0
Accepted
time: 2ms
memory: 3652kb

input:

12
1 1
12 1
12 5
11 5
11 2
8 2
8 6
7 6
7 2
2 2
2 5
1 5
16
0 0
13 0
13 9
4 9
4 4
5 4
5 8
10 8
10 3
9 3
9 7
6 7
6 3
3 3
3 6
0 6

output:

36.7966912753

result:

ok found '36.7966913', expected '36.7966913', error '0.0000000'

Test #13:

score: 0
Accepted
time: 0ms
memory: 3644kb

input:

12
1 1
12 1
12 5
11 5
11 2
8 2
8 6
7 6
7 2
2 2
2 5
1 5
12
0 0
13 0
13 9
4 9
4 4
5 4
5 8
6 8
6 3
3 3
3 6
0 6

output:

33.5214512633

result:

ok found '33.5214513', expected '33.5214513', error '0.0000000'

Test #14:

score: 0
Accepted
time: 2ms
memory: 3788kb

input:

8
1 3
4 2
4 1
5 4
6 4
3 5
3 6
2 3
4
0 0
7 0
7 7
0 7

output:

14.4222051019

result:

ok found '14.4222051', expected '14.4222051', error '0.0000000'

Test #15:

score: 0
Accepted
time: 2ms
memory: 3640kb

input:

8
1 2
2 1
4 3
4 5
5 5
4 6
2 4
2 2
4
2 0
6 4
4 7
0 3

output:

12.9574173292

result:

ok found '12.9574173', expected '12.9574173', error '0.0000000'

Test #16:

score: 0
Accepted
time: 1ms
memory: 3780kb

input:

8
2 2
4 2
6 4
5 5
5 4
3 4
1 2
2 1
4
3 0
7 4
4 6
0 2

output:

12.9574173292

result:

ok found '12.9574173', expected '12.9574173', error '0.0000000'

Test #17:

score: 0
Accepted
time: 2ms
memory: 3620kb

input:

12
1 3
4 2
9 2
9 1
10 4
10 9
11 9
8 10
3 10
3 11
2 8
2 3
4
0 3
9 0
12 9
3 12

output:

33.0451886950

result:

ok found '33.0451887', expected '33.0451887', error '0.0000000'

Test #18:

score: 0
Accepted
time: 2ms
memory: 3636kb

input:

44
21 -7
21 5
20 5
20 -6
17 -6
17 4
16 4
16 -5
13 -5
13 3
12 3
12 -4
9 -4
9 2
8 2
8 -3
5 -3
5 1
4 1
4 -2
1 -2
1 0
-1 0
-1 -2
-4 -2
-4 1
-5 1
-5 -3
-8 -3
-8 2
-9 2
-9 -4
-12 -4
-12 3
-13 3
-13 -5
-16 -5
-16 4
-17 4
-17 -6
-20 -6
-20 5
-21 5
-21 -7
44
22 -8
22 6
19 6
19 -5
18 -5
18 5
15 5
15 -4
14 -4
...

output:

200.7120663779

result:

ok found '200.7120664', expected '200.7120664', error '0.0000000'

Test #19:

score: 0
Accepted
time: 4ms
memory: 3700kb

input:

47
23 -13
22 11
21 -12
20 10
19 -11
18 9
17 -10
16 8
15 -9
14 7
13 -8
12 6
11 -7
10 5
9 -6
8 4
7 -5
6 3
5 -4
4 2
3 -3
2 1
1 -2
0 0
-1 -2
-2 1
-3 -3
-4 2
-5 -4
-6 3
-7 -5
-8 4
-9 -6
-10 5
-11 -7
-12 6
-13 -8
-14 7
-15 -9
-16 8
-17 -10
-18 9
-19 -11
-20 10
-21 -12
-22 11
-23 -13
47
24 -14
22 12
21 -11...

output:

603.5146779550

result:

ok found '603.5146780', expected '603.5146780', error '0.0000000'

Test #20:

score: 0
Accepted
time: 2ms
memory: 3728kb

input:

8
-10 0
-10 -10
0 -10
10 -10
10 0
10 10
0 10
-10 10
8
-20 0
-20 -20
0 -20
20 -20
20 0
20 20
0 20
-20 20

output:

80.0000000000

result:

ok found '80.0000000', expected '80.0000000', error '0.0000000'

Test #21:

score: 0
Accepted
time: 2ms
memory: 3788kb

input:

8
0 10
-10 10
-10 0
-10 -10
0 -10
10 -10
10 0
10 10
8
-20 0
-20 -20
0 -20
20 -20
20 0
20 20
0 20
-20 20

output:

80.0000000000

result:

ok found '80.0000000', expected '80.0000000', error '0.0000000'

Test #22:

score: 0
Accepted
time: 2ms
memory: 3784kb

input:

8
10 0
10 10
0 10
-10 10
-10 0
-10 -10
0 -10
10 -10
8
-20 0
-20 -20
0 -20
20 -20
20 0
20 20
0 20
-20 20

output:

80.0000000000

result:

ok found '80.0000000', expected '80.0000000', error '0.0000000'

Test #23:

score: 0
Accepted
time: 2ms
memory: 3780kb

input:

8
0 -10
10 -10
10 0
10 10
0 10
-10 10
-10 0
-10 -10
8
-20 0
-20 -20
0 -20
20 -20
20 0
20 20
0 20
-20 20

output:

80.0000000000

result:

ok found '80.0000000', expected '80.0000000', error '0.0000000'

Test #24:

score: 0
Accepted
time: 3ms
memory: 3808kb

input:

4
-1000 -1000
0 0
1000 -1000
0 2000
50
1500 -1500
0 2500
-1500 -1500
-460 -730
-440 -720
-420 -710
-400 -700
-380 -690
-360 -680
-340 -670
-320 -660
-300 -650
-280 -640
-260 -630
-240 -620
-220 -610
-200 -600
-180 -590
-160 -580
-140 -570
-120 -560
-100 -550
-80 -540
-60 -530
-40 -520
-20 -510
0 -50...

output:

8560.6232978365

result:

ok found '8560.6232978', expected '8560.6232978', error '0.0000000'

Test #25:

score: 0
Accepted
time: 0ms
memory: 3784kb

input:

4
-1 -1
1 -1
1 1
-1 1
16
1 3
-1 3
-1 2
-2 1
-3 1
-3 -1
-2 -1
-1 -2
-1 -3
1 -3
1 -2
2 -1
3 -1
3 1
2 1
1 2

output:

8.0000000000

result:

ok found '8.0000000', expected '8.0000000', error '0.0000000'

Test #26:

score: 0
Accepted
time: 0ms
memory: 3644kb

input:

8
0 -1
3 -3
1 0
3 3
0 1
-3 3
-1 0
-3 -3
20
0 -2
7 -9
5 -6
6 -5
9 -7
2 0
9 7
6 5
5 6
7 9
0 2
-7 9
-5 6
-6 5
-9 7
-2 0
-9 -7
-6 -5
-5 -6
-7 -9

output:

25.2982212813

result:

ok found '25.2982213', expected '25.2982213', error '0.0000000'

Test #27:

score: 0
Accepted
time: 1ms
memory: 3704kb

input:

5
5 5
3 3
1 5
1 1
5 1
5
0 0
6 0
6 6
3 4
0 6

output:

16.4721359550

result:

ok found '16.4721360', expected '16.4721360', error '0.0000000'

Test #28:

score: 0
Accepted
time: 2ms
memory: 3592kb

input:

12
45 45
135 45
135 108
243 108
162 45
315 45
270 225
189 225
234 117
135 117
162 225
45 108
16
0 0
138 0
138 93
143 98
148 72
211 99
155 44
342 -45
360 270
180 270
192 125
175 122
169 125
161 270
0 180
0 90

output:

1158.3531517499

result:

ok found '1158.3531517', expected '1158.3531517', error '0.0000000'

Test #29:

score: 0
Accepted
time: 1ms
memory: 3644kb

input:

4
-360 180
-297 270
-360 315
-405 225
6
-45 45
-270 270
-90 288
-90 450
-450 495
-540 135

output:

351.5425972393

result:

ok found '351.5425972', expected '351.5425972', error '0.0000000'

Test #30:

score: 0
Accepted
time: 1ms
memory: 3848kb

input:

49
0 -1
460 -1
460 0
450 999
440 0
430 999
420 0
410 999
400 0
390 999
380 0
370 999
360 0
350 999
340 0
330 999
320 0
310 999
300 0
290 999
280 0
270 999
260 0
250 999
240 0
230 999
220 0
210 999
200 0
190 999
180 0
170 999
160 0
150 999
140 0
130 999
120 0
110 999
100 0
90 999
80 0
70 999
60 0
50 ...

output:

46374.3044510818

result:

ok found '46374.3044511', expected '46374.3044511', error '0.0000000'

Test #31:

score: 0
Accepted
time: 3ms
memory: 3656kb

input:

50
-2255 1931
-2830 -3187
3406 -4113
-1883 -1838
2327 -1793
425 -1197
2782 -1197
-569 -601
-6 -1566
-1556 -1182
-793 124
3186 -187
481 523
1688 652
-1844 580
2726 1263
-1544 1419
2655 1961
-389 1916
2623 2899
-3785 4421
-4440 3211
-2902 3483
-4580 -3486
-2403 3382
-537 3211
425 2728
-1005 2345
-1696...

output:

67111.7337451839

result:

ok found '67111.7337452', expected '67111.7337452', error '0.0000000'

Test #32:

score: 0
Accepted
time: 3ms
memory: 3752kb

input:

50
-4856 -2492
2539 -4838
4880 4847
-4864 -2066
2295 -4254
4404 4050
-4153 -1952
2123 -3843
3981 3355
-3486 -1880
1931 -3331
3514 2614
-2659 -1781
1764 -2833
3058 1817
-1907 -1667
1540 -2336
2515 1035
-1144 -1509
1404 -1895
2059 295
-389 -1338
1220 -1509
1540 -442
373 -1155
1084 -1167
661 -1083
1468...

output:

258611.4291814968

result:

ok found '258611.4291815', expected '258611.4291815', error '0.0000000'

Test #33:

score: 0
Accepted
time: 3ms
memory: 3664kb

input:

50
1744 1847
-3538 3666
-3761 -4197
3609 -3486
4065 1874
1148 -2860
-1480 -3403
-2523 2444
-2299 -2917
-3050 -358
-2235 -3600
1456 -3046
3366 -160
3206 -3217
-3382 -3972
-2627 -3187
-3677 -3274
-3178 253
-2703 -571
-3370 3028
-2119 2800
-1068 -2548
2143 -912
-433 -643
-741 1521
-1037 -2420
-805 1646...

output:

55761.8456172589

result:

ok found '55761.8456173', expected '55761.8456173', error '0.0000000'

Test #34:

score: 0
Accepted
time: 0ms
memory: 3616kb

input:

50
-4197 3951
885 2572
-3773 3127
-3294 -3459
-2710 2474
-2862 -3900
-3933 -3642
-4293 -4340
4392 -4355
-2255 -3786
-2235 2330
3374 1305
-1428 -3331
3026 340
3194 -3558
-1684 -3471
2822 1107
-1939 1889
-2011 -3558
4848 -4325
4373 4334
1104 1874
-2299 2486
-2363 -4128
-2607 2557
-2798 2587
-3286 -247...

output:

114150.0917307214

result:

ok found '114150.0917307', expected '114150.0917307', error '0.0000000'

Test #35:

score: 0
Accepted
time: 4ms
memory: 3696kb

input:

50
-4704 -4583
2 4349
4616 -4667
2962 4706
-3697 4562
-4920 -4766
-805 -3984
-1080 -1224
417 -942
2091 -3729
-70 -2150
405 -3630
1456 -4340
2726 -4140
2411 -2860
1160 -885
142 -46
174 708
54 1206
-729 253
-421 -373
-1716 -472
-1005 978
-190 2018
301 1634
765 735
521 397
1033 10
1096 735
757 1832
46 ...

output:

43688.2184848068

result:

ok found '43688.2184848', expected '43688.2184848', error '0.0000000'

Test #36:

score: 0
Accepted
time: 1ms
memory: 3724kb

input:

50
-4325 -4311
3769 3951
-3921 -4367
3470 2713
-3318 -4595
4752 -4526
661 -1212
4077 -4311
-2619 -4284
3270 -3915
-2351 -3942
2846 -3573
206 -1224
4213 2926
4712 -3999
861 -1011
4904 -4269
4680 4604
-2978 -3444
4572 4661
-4876 4691
-4792 -4481
-4684 4520
-4652 -4412
-4440 4406
4105 4478
-4229 4080
3...

output:

131797.0929148330

result:

ok found '131797.0929148', expected '131797.0929148', error '0.0000000'

Test #37:

score: 0
Accepted
time: 0ms
memory: 3688kb

input:

50
-1400 0
900 1839
795 1976
682 2096
564 2197
440 2279
313 2340
182 2380
50 2399
-81 2396
-213 2373
-342 2327
-469 2262
-592 2176
-709 2070
-820 1946
-923 1805
-1019 1647
-1105 1475
-1181 1290
-1247 1093
-1302 886
-1345 671
-1376 451
-1394 226
-1401 0
-1394 -226
-1376 -451
-1345 -671
-1302 -886
-12...

output:

13435.2525506440

result:

ok found '13435.2525506', expected '13435.2525506', error '0.0000000'

Test #38:

score: 0
Accepted
time: 0ms
memory: 3672kb

input:

50
-4832 -4823
-2311 4706
4784 -2435
-4600 -4640
-2183 4236
4137 -2321
-4313 -4311
-2075 3738
3514 -2177
-4061 -4041
-1971 3241
3162 -2093
-3877 -3858
-1883 2770
2750 -1964
-3665 -3642
-1800 2474
2251 -1838
-3382 -3346
-1696 2075
1772 -1724
-3138 -3145
-1620 1661
1360 -1622
-2922 -2890
1552 -1667
-1...

output:

30903.7743764705

result:

ok found '30903.7743765', expected '30903.7743765', error '0.0000000'