QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#792493#784. 旋转卡壳zhouyuhang0 0ms27240kbC++141.6kb2024-11-29 10:50:392024-11-29 10:50:40

Judging History

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

  • [2024-11-29 10:50:40]
  • 评测
  • 测评结果:0
  • 用时:0ms
  • 内存:27240kb
  • [2024-11-29 10:50:39]
  • 提交

answer

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

const int N = 5e5 + 10;

struct Po {
	double x, y;
	Po(double X = 0.0, double Y = 0.0) {
		x = X, y = Y;
	}
};
Po operator -(Po a, Po b) {
	return Po(a.x - b.x, a.y - b.y); 
}
double operator *(Po a, Po b) {
	return a.x * b.y - a.y * b.x;
}
double dis(Po a, Po b) {
	Po d = a - b;
	return sqrt(d.x * d.x + d.y * d.y); 
}
double area(vector<Po> v) {
	double ret = 0.0;
	for (int i = 0; i < v.size(); ++i) ret += v[i] * v[(i + 1) % v.size()];
	return ret < 0.0 ? -ret / 2 : ret / 2;
}

int n;
Po p[N];

Po st[N], cvx[N];
int top = 0, l = 0;

int main() {
	cin >> n;
	for (int i = 1; i <= n; ++i) cin >> p[i].x >> p[i].y;
	sort(p + 1, p + n + 1, [&](Po a, Po b) { return a.x == b.x ? a.y < b.y : a.x < b.x;});
	
	st[top = 1] = p[1];
	for (int i = 2; i <= n; ++i) {
		while (top > 1 && (st[top] - st[top - 1]) * (p[i] - st[top - 1]) <= 0.0) --top;
		st[++top] = p[i];
	}
	for (int i = 1; i < top; ++i) cvx[++l] = st[i];
	st[top = 1] = p[n];
	for (int i = n - 1; ~i; --i) {
		while (top > 1 && (st[top] - st[top - 1]) * (p[i] - st[top - 1]) <= 0.0) --top;
		st[++top] = p[i];
	}
	for (int i = 1; i < top; ++i) cvx[++l] = st[i];
	
	n = l;
	for (int i = 1; i <= n; ++i) p[i] = cvx[i];
	
	double ans = 0;
	for (int i = 1, j = 3; i <= n; ++i) {
		while (area({p[i], p[i % n + 1], p[j % n + 1]}) > area({p[i], p[i % n + 1], p[j]})) j = j % n + 1;
		ans = max(ans, dis(p[i], p[j]));
		ans = max(ans, dis(p[i], p[j % n + 1]));
	}
	cout << fixed << setprecision(10) << ans << endl;

    return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Subtask #1:

score: 0
Wrong Answer

Test #1:

score: 0
Wrong Answer
time: 0ms
memory: 27240kb

input:

1000
0 0
-997615 -8573
-1988394 -28911
-2726572 -44296
-3491635 -60392
-4419752 -82814
-5298550 -105946
-5723430 -118453
-6608257 -147267
-7034966 -161982
-7563964 -181682
-8507871 -222865
-9499799 -271846
-10090186 -303547
-10400262 -322989
-10614073 -339725
-11081438 -378596
-11791568 -439127
-127...

output:

274335204.2868217230

result:

wrong answer 1st numbers differ - expected: '274339223.1895614', found: '274335204.2868217', error = '0.0000146'

Subtask #2:

score: 0
Skipped

Dependency #1:

0%

Subtask #3:

score: 0
Skipped

Dependency #1:

0%