QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#341040#7730. Convex CheckerJsxts_#WA 1ms3608kbC++141.4kb2024-02-29 15:09:442024-02-29 15:09:44

Judging History

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

  • [2024-07-04 19:27:17]
  • hack成功,自动添加数据
  • (/hack/727)
  • [2024-07-04 19:17:30]
  • hack成功,自动添加数据
  • (/hack/726)
  • [2024-02-29 15:09:44]
  • 评测
  • 测评结果:WA
  • 用时:1ms
  • 内存:3608kb
  • [2024-02-29 15:09:44]
  • 提交

answer

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int inf = 1e9;
const ll INF = 1e15;
const int N = 2e5;
inline int read() {
	int s = 0,f = 1;char ch = getchar();
	while (!isdigit(ch)) f = ch == '-' ? -1 : 1, ch = getchar();
	while (isdigit(ch)) s = (s << 3) + (s << 1) + ch - '0', ch = getchar();
	return s*f;
}
struct vec {
	int x,y;
	friend vec operator - (vec x,vec y) {
		return {x.x - y.x,x.y - y.y};
	}
}a[N + 10],st[N + 10];
int top;
ll cross(vec x,vec y) {
	return 1ll * x.x * y.y - 1ll * x.y * y.x;
}
ll calc(vec x,vec y,vec k) {
	return cross(y - x,k - x);
}
double dis(vec x,vec y) {
	return sqrt(((double)x.x - y.x) * (x.x - y.x) + ((double)x.y - y.y) * (x.y - y.y));
}
int cmp(vec x,vec y) {
	return x.x == y.x ? x.y < y.y : x.x < y.x;
}
int main() {
	int n = read();
	ll s = 0;
	for (int i = 1;i <= n;i ++ ) a[i].x = read(), a[i].y = read();
	for (int i = 1;i <= n;i ++ ) s += cross(a[i],a[i % n + 1]);
	sort(a + 1,a + n + 1,cmp);
	for (int i = 1;i <= n;i ++ ){
		while (top > 1 && calc(st[top - 1],st[top],a[i]) <= 0) top --;
		st[++top] = a[i];
	}
	int tp = top;
	for (int i = n - 1;i;i -- ) {
		while (top > tp && calc(st[top - 1],st[top],a[i]) <= 0) top --;
		st[++top] = a[i];
	}
	ll s2 = 0;
	for (int i = 1;i <= top;i ++ ) s2 += cross(st[i],st[i % top + 1]);
	if (top - 1 == n && s == s2) puts("Yes");
	else puts("No");
	return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 1ms
memory: 3608kb

input:

3
0 0
1 0
0 1

output:

Yes

result:

ok answer is YES

Test #2:

score: -100
Wrong Answer
time: 1ms
memory: 3496kb

input:

4
0 0
0 1
1 1
1 0

output:

No

result:

wrong answer expected YES, found NO