QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#532695#784. 旋转卡壳RainSky0 0ms5832kbC++142.4kb2024-08-25 09:31:222024-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:23]
  • 评测
  • 测评结果:0
  • 用时:0ms
  • 内存:5832kb
  • [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%