QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#341030#7730. Convex CheckerJsxts_#WA 0ms3692kbC++141.2kb2024-02-29 15:06:152024-02-29 15:06:17

Judging History

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

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

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();
	for (int i = 1;i <= n;i ++ ) a[i].x = read(), a[i].y = read();
	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];
	}
	if (top - 1 == n) puts("Yes");
	else puts("No");
	return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 0ms
memory: 3660kb

input:

3
0 0
1 0
0 1

output:

Yes

result:

ok answer is YES

Test #2:

score: 0
Accepted
time: 0ms
memory: 3692kb

input:

4
0 0
0 1
1 1
1 0

output:

Yes

result:

ok answer is YES

Test #3:

score: 0
Accepted
time: 0ms
memory: 3612kb

input:

4
0 0
0 3
1 2
1 1

output:

Yes

result:

ok answer is YES

Test #4:

score: 0
Accepted
time: 0ms
memory: 3488kb

input:

3
0 0
0 0
0 0

output:

No

result:

ok answer is NO

Test #5:

score: -100
Wrong Answer
time: 0ms
memory: 3548kb

input:

5
1 0
4 1
0 1
2 0
3 2

output:

Yes

result:

wrong answer expected NO, found YES