QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#792493 | #784. 旋转卡壳 | zhouyuhang | 0 | 0ms | 27240kb | C++14 | 1.6kb | 2024-11-29 10:50:39 | 2024-11-29 10:50:40 |
Judging History
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%