QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#31732#21645. 是男人就得80分问题Qingyu100 ✓353ms4468kbC++205.7kb2022-05-11 23:27:252022-05-11 23:27:27

Judging History

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

  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2022-05-11 23:27:27]
  • 评测
  • 测评结果：100
  • 用时：353ms
  • 内存：4468kb
查看
  • [2022-05-11 23:27:25]
  • 提交

answer

#include<bits/stdc++.h>
#define eps 1e-4
using namespace std;
struct point {
	double x, y;
	point(double a = 0, double b = 0):x(a),y(b){}
};
point operator+(point a, point b) {
	return point(a.x+b.x, a.y+b.y);
}
point operator-(point a, point b) {
	return point(a.x-b.x, a.y-b.y);
}
point operator-(point a) {
	return point(-a.x, -a.y);
}
double cross(point a, point b) {
	return a.x*b.y-a.y*b.x;
}
double dis(point a) {
	return sqrt(a.x*a.x+a.y*a.y);
}
struct polygon {
	int n;
	point p[55];
	struct triangle {
		int a[3];
		triangle(int x, int y, int z){
			a[0] = x, a[1] = y, a[2] = z;
		}
	};
	vector<triangle> cut;
	void shift(point dir) {
		for (int i = 0; i <= n+1; i++) p[i] = p[i] + dir;
	}
	void rotate(double theta) {
		for (int i = 0; i <= n+1; i++) {
			double x0 = p[i].x*cos(theta)-p[i].y*sin(theta);
			double y0 = p[i].x*sin(theta)+p[i].y*cos(theta);
			p[i].x = x0, p[i].y = y0;
		}
	}
	void split() {
		if (n == 3) {
			cut.push_back(triangle(1, 2, 3));
			return;
		}
		triangle res(0,0,0);
		double minarea = 0x3f3f3f3f;
		for (int i = 1; i <= n; i++) {
			point tmp;
			if (i == 1) tmp = p[n-1];
			else tmp = p[i-2];
			if (cross(p[i-1]-tmp, p[i]-tmp) < 0) {
				if (cross(p[i-1]-tmp, p[i+1]-p[i-1]) >= 0 || cross(p[i]-p[i-1], p[i+1]-p[i-1]) >= 0) continue;
			}
			else {
				if (cross(p[i-1]-tmp, p[i+1]-p[i-1]) >= 0 && cross(p[i]-p[i-1], p[i+1]-p[i-1]) >= 0) continue;
			}
			bool flag = 1;
			for (int j = 1; j <= n && flag; j++)
				if (j!=i&&j!=i-1&&j!=i-2&&j!=i+1&&!(i==1&&j==n)&&!(i==2&&j==n)&&!(i==1&&j==n-1)&&!(i==n&&j==1))
					if (cross(p[i-1]-p[i+1],p[j]-p[i+1])*cross(p[i-1]-p[i+1],p[j+1]-p[i+1]) <= 0
						&& cross(p[j]-p[j+1],p[i-1]-p[j+1])*cross(p[j]-p[j+1],p[i+1]-p[j+1]) < 0) flag = 0;
			if (flag) {
				res = triangle(i-1, i, i+1);
				break;
			}
		}
		assert(res.a[1]);
		if (res.a[0] == 0) res.a[0] = n;
		if (res.a[2] == n+1) res.a[2] = 1;
		cut.push_back(res);
		polygon nxt;
		nxt.n = n - 1;
		for (int i = 1; i < n; i++) nxt.p[i] = p[(i+res.a[0])%n+1];
		nxt.p[0] = nxt.p[n-1], nxt.p[n] = nxt.p[1];
		nxt.split();
		for (auto i : nxt.cut) {
			triangle tmp((i.a[0]+res.a[0])%n+1, (i.a[1]+res.a[0])%n+1, (i.a[2]+res.a[0])%n+1);
			cut.push_back(tmp);
		}
	}
}p1, p2;
struct event {
	double t, len;
	int typ;
}e[10001];
bool operator<(const event &a, const event &b) {
	if (fabs(a.t - b.t) < eps) return a.typ < b.typ;
	return a.t < b.t;
}
double work() {
	int tot = 0;
	for (auto i : p1.cut)
		for (auto j : p2.cut) {
			double l = 1e5, r = -1e5;
			point k1[4], k2[4];
			for (int x = 0; x < 3; x++) k1[x] = p1.p[i.a[x]], k2[x] = p2.p[j.a[x]];
			k1[3] = k1[0], k2[3] = k2[0];
			if (max(min(k1[1].x, min(k1[2].x, k1[3].x)), min(k2[1].x, min(k2[2].x, k2[3].x)))
				- min(max(k1[1].x, max(k1[2].x, k1[3].x)), max(k2[1].x, max(k2[2].x, k2[3].x))) > -eps) continue;
			for (int x = 0; x < 3; x++)
				for (int y = 0; y < 3; y++) {
					if (fabs(k1[x].x-k2[y].x) < eps) l = min(l, k2[y].y-k1[x].y), r = max(r, k2[y].y-k1[x].y);
					if ((k1[x].x-k2[y].x)*(k1[x].x-k2[y+1].x) < 0) {
						double t = (k2[y+1].y-k2[y].y)/(k2[y+1].x-k2[y].x)*(k1[x].x-k2[y].x)+k2[y].y-k1[x].y;
						l = min(l, t), r = max(r, t);
					}
					if ((k2[y].x-k1[x].x)*(k2[y].x-k1[x+1].x) < 0) {
						double t = k2[y].y-(k1[x+1].y-k1[x].y)/(k1[x+1].x-k1[x].x)*(k2[y].x-k1[x].x)-k1[x].y;
						l = min(l, t), r = max(r, t);
					}
				}
			if (l < r) {
				++tot, e[tot].t = l, e[tot].typ = 1;
				++tot, e[tot].t = r, e[tot].typ = -1;
			}
		}
	for (int i = 1; i <= p1.n; i++)
		for (int j = 1; j <= p2.n; j++)
			if (fabs(cross(p1.p[i+1]-p1.p[i], p2.p[j+1]-p2.p[j])) < eps) {
				if (fabs(p1.p[i+1].x-p1.p[i].x) < eps) {
					if (fabs(p1.p[i].x-p2.p[j].x) > eps) continue;
					++tot, e[tot].t = min(p2.p[j].y, p2.p[j+1].y)-max(p1.p[i].y, p1.p[i+1].y), e[tot].typ = 2;
					++tot, e[tot].t = min(p2.p[j].y, p2.p[j+1].y)-min(p1.p[i].y, p1.p[i+1].y), e[tot].typ = -2;
					++tot, e[tot].t = max(p2.p[j].y, p2.p[j+1].y)-max(p1.p[i].y, p1.p[i+1].y), e[tot].typ = -2;
					++tot, e[tot].t = max(p2.p[j].y, p2.p[j+1].y)-min(p1.p[i].y, p1.p[i+1].y), e[tot].typ = 2;
				}
				else {
					double x1 = p1.p[i].x, x2 = p1.p[i+1].x, x3 = p2.p[j].x, x4 = p2.p[j+1].x;
					if (x1 > x2) swap(x1, x2);
					if (x3 > x4) swap(x3, x4);
					double dis = min(x2, x4) - max(x1, x3), k = (p1.p[i+1].y-p1.p[i].y)/(p1.p[i+1].x-p1.p[i].x);
					if (dis <= eps) continue;
					++tot, e[tot].t = k*(p1.p[i].x-p2.p[j].x)+p2.p[j].y-p1.p[i].y, e[tot].typ = 0, e[tot].len = dis*sqrt(1+k*k);
				}
			}
	sort(e + 1, e + tot + 1);
	double ans = 0, b = 0, tmp = 0;
	int cnt = 0, k = 0;
	for (int i = 1; i <= tot; i++) {
		if (!cnt) ans = max(ans, e[i].t*k+b+tmp);
		if (i == 1 || fabs(e[i].t - e[i-1].t) > eps) tmp = 0;
		if (e[i].typ == -2) b += e[i].t, --k;
		if (e[i].typ == -1) --cnt;
		if (e[i].typ == 0) tmp += e[i].len;
		if (e[i].typ == 1) ++cnt;
		if (e[i].typ == 2) b -= e[i].t, ++k;
		if (!cnt) ans = max(ans, e[i].t*k+b+tmp);
	}
	return ans;
}
int main() {
	cin >> p1.n;
	for (int i = 1; i <= p1.n; i++) cin >> p1.p[i].x >> p1.p[i].y;
	p1.p[0] = p1.p[p1.n], p1.p[p1.n+1] = p1.p[1];
	cin >> p2.n;
	for (int i = 1; i <= p2.n; i++) cin >> p2.p[i].x >> p2.p[i].y;
	p2.p[0] = p2.p[p2.n], p2.p[p2.n+1] = p2.p[1];
	p1.split(), p2.split();
	polygon b1 = p1, b2 = p2;
	double ans = 0;
	for (int i = 1; i <= p1.n; i++)
		for (int j = 1; j <= p2.n; j++) {
			p1 = b1, p2 = b2;
			p1.shift(-p1.p[i]), p2.shift(-p2.p[j]);
			p1.rotate(atan2(p1.p[i+1].x-p1.p[i].x, p1.p[i+1].y-p1.p[i].y));
			p2.rotate(atan2(p2.p[j].x-p2.p[j+1].x, p2.p[j].y-p2.p[j+1].y));
			ans = max(ans, work());
		}
	cout << fixed << setprecision(9) << ans << endl;
}
Source code, Language: C++20

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 10
Accepted
time: 3ms
memory: 4284kb

input:

3
40 0
0 0
0 30
3
10 0
0 -40
-10 0

output:

41.231056256

result:

ok found '41.23106', expected '41.23106', error '0.00000'

Test #2:

score: 10
Accepted
time: 0ms
memory: 4336kb

input:

4
-20 0
0 20
20 0
0 -20
4
15 15
15 -15
-15 -15
-15 15

output:

28.284271247

result:

ok found '28.28427', expected '28.28427', error '0.00000'

Test #3:

score: 10
Accepted
time: 1ms
memory: 4300kb

input:

8
0 0
0 1
1 100
1 1
2 100
2 1
3 100
3 0
8
100 0
99 0
0 1
99 1
0 2
99 2
0 3
100 3

output:

495.015151129

result:

ok found '495.01515', expected '495.01515', error '0.00000'

Test #4:

score: 10
Accepted
time: 0ms
memory: 4236kb

input:

8
0 0
50 0
50 -10
30 -10
30 -50
20 -50
20 -10
0 -10
8
0 50
50 100
70 80
40 50
50 40
80 70
100 50
50 0

output:

75.857864376

result:

ok found '75.85786', expected '75.85786', error '0.00000'

Test #5:

score: 10
Accepted
time: 5ms
memory: 4468kb

input:

11
0 24
6 60
12 24
18 48
24 18
30 36
36 24
48 72
48 24
36 0
12 0
19
-60 -50
-60 46
60 70
48 12
48 34
-16 34
0 46
-24 34
12 16
-36 10
0 4
-24 -2
-12 -8
-48 -2
0 -26
40 -6
41 -5
48 10
96 -14

output:

49.477267507

result:

ok found '49.47727', expected '49.47727', error '0.00000'

Test #6:

score: 10
Accepted
time: 4ms
memory: 4232kb

input:

16
-1 2
0 1
1 2
1 1
2 1
1 0
2 -1
1 -1
1 -2
0 -1
-1 -2
-1 -1
-2 -1
-1 0
-2 1
-1 1
16
5 40
20 30
30 20
40 5
40 -5
30 -20
20 -30
5 -40
-5 -40
-20 -30
-30 -20
-40 -5
-40 5
-30 20
-20 30
-5 40

output:

0.000000000

result:

ok found '0.00000', expected '0.00000', error '-0.00000'

Test #7:

score: 10
Accepted
time: 5ms
memory: 4308kb

input:

11
6 0
4 0
0 10
0 20
10 20
20 22
20 -50
15 -50
14 -17
15 10
10 10
11
6 0
4 0
0 10
0 20
15 30
30 35
27 -7
20 -50
20 24
10 20
10 10

output:

54.000000000

result:

ok found '54.00000', expected '54.00000', error '0.00000'

Test #8:

score: 10
Accepted
time: 3ms
memory: 4284kb

input:

11
0 0
-50 0
-50 10
-49 10
-49 3
-20 3
-20 4
49 4
49 10
50 10
50 1
6
0 0
0 1
60 61
61 61
61 60
1 0

output:

68.292893219

result:

ok found '68.29289', expected '68.29289', error '0.00000'

Test #9:

score: 10
Accepted
time: 353ms
memory: 4392kb

input:

50
0 10
2 11
4 10
6 11
8 10
10 11
12 10
14 11
16 10
18 11
20 10
22 11
24 10
26 11
28 10
30 11
32 10
34 11
38 10
40 11
42 10
44 11
48 10
49 11
49 0
47 1
45 0
43 1
41 0
39 1
37 0
35 1
33 0
31 1
29 0
25 1
23 0
21 1
19 0
17 1
15 0
13 1
11 0
9 1
7 0
6 1
5 0
3 1
1 0
0 0
50
0 10
2 11
4 10
6 11
8 10
10 11
1...

output:

29.068883707

result:

ok found '29.06888', expected '29.06888', error '0.00000'

Test #10:

score: 10
Accepted
time: 270ms
memory: 4380kb

input:

49
-25 -10
-24 -23
-32 -9
-29 -48
-39 -68
-22 -79
-24 -53
-16 -82
13 -94
9 -42
9 -27
5 -30
4 -57
-7 -54
-16 -32
-20 20
-11 18
-6 -47
-6 -52
2 -56
3 -29
13 -24
15 -35
19 -87
21 -88
17 -36
60 15
33 11
31 37
32 59
21 52
25 0
-5 -10
-7 16
13 41
-17 51
-20 90
-39 77
-35 25
-40 35
-37 -4
-44 77
-19 92
33 ...

output:

430.953590576

result:

ok found '430.95359', expected '430.95359', error '0.00000'

Extra Test:

score: 0
Extra Test Passed
English 繁體中文 简体中文

Server Time: 2024-12-05 04:32:16 | OpenSource Project