QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#341041 | #7730. Convex Checker | Jsxts_# | WA | 1ms | 5772kb | C++14 | 1.4kb | 2024-02-29 15:10:13 | 2024-02-29 15:10:14 |
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();
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 + 1]);
if (top - 1 == n && s == s2) puts("Yes");
else puts("No");
return 0;
}
详细
Test #1:
score: 100
Accepted
time: 0ms
memory: 5644kb
input:
3 0 0 1 0 0 1
output:
Yes
result:
ok answer is YES
Test #2:
score: -100
Wrong Answer
time: 1ms
memory: 5772kb
input:
4 0 0 0 1 1 1 1 0
output:
No
result:
wrong answer expected YES, found NO