QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#341121 | #7730. Convex Checker | Yansuan_HCl# | WA | 1ms | 3652kb | C++14 | 1.3kb | 2024-02-29 15:55:48 | 2024-02-29 15:55:48 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
#define IC isdigit(c)
#define GC c=getchar()
void rd(auto &x) { char GC; x = 0; bool f = 0;
for (; !IC; GC) if (c == '-') f = 1;
for (; IC; GC) x = x * 10 + c - 48;
if (f) x = -x;
}
void rd(auto &x, auto &...y) { rd(x); rd(y...); }
#define U(i,l,r) for(int i(l),END##i(r); i<=END##i; ++i)
#define D(i,l,r) for(int i(l),END##i(r); i>=END##i; --i)
#define ms(x, v) memset(x, v, sizeof(x))
#define meow(...) fprintf(stderr, __VA_ARGS__)
using ll = long long;
const int N = 200005;
#define x real()
#define y imag()
using P = complex<ll>;
P p[N]; int n;
int main() {
// freopen("arrebol.in", "r", stdin);
rd(n);
U (i, 1, n) {
ll a, b; rd(a, b);
p[i] = {a, b};
}
sort(p + 1, p + n + 1, [&](const P &l, const P &r) {
return l.x == r.x ? l.y < r.y : l.x < r.x;
});
U (i, 2, n) if (p[i] == p[i - 1]) {
puts("No");
exit(0);
}
D (i, n, 1) p[i] -= p[1];
sort(p + 1, p + n + 1, [&](const P &l, const P &r) {
ll cx = l.x * r.y - l.y * r.x;
if (cx == 0) return l.x < r.x;
return cx < 0;
});
p[n + 1] = p[1];
int stk[N] {}, sp = 2; stk[1] = 1, stk[2] = 2;
U (i, 3, n + 1) {
P p1 = p[stk[sp]] - p[stk[sp - 1]], p2 = p[i] - p[stk[sp]];
if (p1.x * p2.y - p1.y * p2.x >= 0) {
puts("No");
exit(0);
}
stk[++sp] = i;
}
puts("Yes");
}
详细
Test #1:
score: 100
Accepted
time: 1ms
memory: 3632kb
input:
3 0 0 1 0 0 1
output:
Yes
result:
ok answer is YES
Test #2:
score: 0
Accepted
time: 0ms
memory: 3488kb
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: 3592kb
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: 3652kb
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