QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#341030 | #7730. Convex Checker | Jsxts_# | WA | 0ms | 3692kb | C++14 | 1.2kb | 2024-02-29 15:06:15 | 2024-02-29 15:06:17 |
Judging History
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;
}
詳細信息
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