QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#422537 | #7730. Convex Checker | GoatGirl98 | WA | 1ms | 3812kb | C++14 | 1.8kb | 2024-05-27 15:40:52 | 2024-05-27 15:40:53 |
Judging History
answer
#include <stdio.h>
#include <math.h>
#include <vector>
typedef long long i64;
int rd()
{
int k = 0, f = 1;
char c = getchar();
while (c < '0' || c > '9')
{
if (c == '-')
f = 0;
c = getchar();
}
while (c >= '0' && c <= '9')
{
k = (k << 1) + (k << 3) + (c ^ '0');
c = getchar();
}
return f ? k : -k;
}
struct point
{
int x, y;
int idx;
point(int _x = 0, int _y = 0, int id = 0) : x(_x), y(_y), idx(id) {}
void input() { x = rd(), y = rd(); }
point operator-(const point &o) const { return point(x - o.x, y - o.y); }
// point product of vector
i64 operator*(const point & o) const { return 1ll * x * o.x + 1ll * y * o.y; }
// cross product of vector
i64 operator^(const point &o) const { return 1ll * x * o.y - 1ll * y * o.x; }
bool operator<(const point &o) const { return (x ^ o.x) ? (x < o.x) : (y < o.y); }
bool operator==(const point &o) const { return (x == o.x) && (y == o.y); }
};
bool isconvex(const std::vector<point>& pts)
{
int n = (int) pts.size();
if (n <= 2)
return false;
i64 cross = (pts[0] - pts[n - 1]) ^ (pts[n - 1] - pts[n - 2]);
if (cross == 0)
return false;
bool dir = cross > 0;
cross = (pts[1] - pts[0]) ^ (pts[0] - pts[n - 1]);
if ((cross == 0) || ((cross > 0) != dir))
return false;
for (int i = 2; i < n; ++i)
{
cross = (pts[i] - pts[i - 1]) ^ (pts[i - 1] - pts[i - 2]);
if ((cross == 0) || ((cross > 0) != dir))
return false;
}
return true;
}
int main()
{
int n = rd();
std::vector<point> pts(n);
for (int i = 0; i < n; ++i)
pts[i].x = rd(), pts[i].y = rd();
puts(isconvex(pts) ? "Yes" : "No");
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 0ms
memory: 3768kb
input:
3 0 0 1 0 0 1
output:
Yes
result:
ok answer is YES
Test #2:
score: 0
Accepted
time: 1ms
memory: 3592kb
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: 3812kb
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: 3536kb
input:
3 0 0 0 0 0 0
output:
No
result:
ok answer is NO
Test #5:
score: -100
Wrong Answer
time: 1ms
memory: 3540kb
input:
5 1 0 4 1 0 1 2 0 3 2
output:
Yes
result:
wrong answer expected NO, found YES