QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#532695 | #784. 旋转卡壳 | RainSky | 0 | 0ms | 5832kb | C++14 | 2.4kb | 2024-08-25 09:31:22 | 2024-08-25 09:31:23 |
Judging History
你现在查看的是最新测评结果
- [2024-10-16 12:18:36]
- hack成功,自动添加数据
- (/hack/1005)
- [2024-09-24 16:55:39]
- hack成功,自动添加数据
- (/hack/888)
- [2024-08-25 09:31:22]
- 提交
answer
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> PII;
#define Point Vector
#define fir first
#define sec second
#define ep emplace
#define eb emplace_back
struct Vector {
int x, y;
Vector(int x = 0, int y = 0): x(x), y(y) {};
Vector operator + (Vector b) { return Vector(x + b.x, y + b.y); }
Vector operator - (Vector b) { return Vector(x - b.x, y - b.y); }
Vector operator * (int k) { return Vector(x * k, y * k); }
Vector operator / (int k) { return Vector(x / k, y / k); }
double length() { return sqrt(x * x + y * y); }
int dot(Vector b) { return x * b.x + y * b.y; }
int prod(Vector b) { return x * b.y - y * b.x; }
Vector rotate(double t) { return Vector(x * cos(t) - y * sin(t), y * cos(t) + x * sin(t)); }
double angle(Vector b) {
if (!b.length()) return -1e9;
double theta = acos(dot(b) / length() / b.length());
if (prod(b) < 0) theta = -theta;
return theta;
}
};
#define lowbit(x) ((x) & (-(x)))
inline int read() {
int x = 0, f = 1; char ch = getchar();
for (; !isdigit(ch); ch = getchar()) if (ch == '-') f = -1;
for (; isdigit(ch); ch = getchar()) x = (x << 1) + (x << 3) + (ch ^ 48);
return x * f;
}
const int N = 100010;
const double eps = 1e-9;
int n, top;
Point pt[N], st[N];
bool cmp1(Point a, Point b) {
if (a.x != b.x) return a.x < b.x;
return a.y < b.y;
}
bool cmp2(Point a, Point b) {
double ta = atan2(a.y, a.x), tb = atan2(b.y, b.x);
if (!a.length()) ta = -1e9;
if (!b.length()) tb = -1e9;
if (fabs(ta - tb) > eps) return ta < tb;
return a.length() < b.length();
}
int main() {
n = read();
for (int i = 1; i <= n; i ++ ) {
int x = read(), y = read();
pt[i] = Point(x, y);
}
Point O = *min_element(pt + 1, pt + n + 1, cmp1);
for (Point &x : pt) x = x - O;
sort(pt + 1, pt + n + 1, cmp2);
st[ ++ top] = pt[1];
for (int i = 2; i <= n; i ++ ) {
while (top > 1 && (st[top] - st[top - 1]).prod(pt[i] - st[top]) <= 0) top -- ;
st[ ++ top] = pt[i];
}
for (int i = 1; i <= top; i ++ ) st[i + top] = st[i];
top <<= 1;
Vector vec = st[1];
int ans = 0;
for (int i = 1, j = 1; i <= top; i ++ ) {
while (j < i) vec = vec + st[j + 1] - st[j], j ++ ;
while (j < top && vec.dot(st[j + 1] - st[j]) >= 0) vec = vec + st[j + 1] - st[j], j ++ ;
ans = max(ans, vec.x * vec.x + vec.y * vec.y);
vec = vec - (st[i] - st[i - 1]);
}
printf("%d\n", ans);
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: 5832kb
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:
2094458440
result:
wrong answer 1st numbers differ - expected: '274339223.1895614', found: '2094458440.0000000', error = '6.6345570'
Subtask #2:
score: 0
Skipped
Dependency #1:
0%
Subtask #3:
score: 0
Skipped
Dependency #1:
0%