QOJ.ac
QOJ
ID | 提交记录ID | 题目 | Hacker | Owner | 结果 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|
#726 | #422540 | #7730. Convex Checker | Qingyu | GoatGirl98 | Success! | 2024-07-04 19:17:19 | 2024-07-04 19:17:19 |
详细
Extra Test:
Wrong Answer
time: 6ms
memory: 4272kb
input:
63106 142555391 -989786825 142628513 -989776291 142733479 -989761159 142876092 -989740583 143089114 -989709808 143192330 -989694880 143443376 -989658525 143457992 -989656407 143512227 -989648543 143552582 -989642691 143828488 -989602630 143882018 -989594848 143928651 -989588067 144020124 -989574759 ...
output:
No
result:
wrong answer expected YES, found NO
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#422540 | #7730. Convex Checker | GoatGirl98 | WA | 11ms | 4792kb | C++14 | 2.3kb | 2024-05-27 15:47:07 | 2024-07-04 19:18:15 |
answer
#include <stdio.h>
#include <math.h>
#include <vector>
typedef long long i64;
const double PI = acos(-1.0);
const double eps = 1e-7;
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); }
double len() const { return sqrt(1ll * x * x + 1ll * y * 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); }
};
// using point as vector
double angle(const point &a, const point &b) { return acos(1.0 * (a * b) / (a.len() * b.len())); }
bool isconvex(const std::vector<point> &pts)
{
int n = (int)pts.size();
if (n <= 2)
return false;
double exterior_angle = 0.0;
i64 cross = (pts[0] - pts[n - 1]) ^ (pts[n - 1] - pts[n - 2]);
if (cross == 0)
return false;
bool dir = cross > 0;
exterior_angle += angle(pts[0] - pts[n - 1], pts[n - 1] - pts[n - 2]);
cross = (pts[1] - pts[0]) ^ (pts[0] - pts[n - 1]);
if ((cross == 0) || ((cross > 0) != dir))
return false;
exterior_angle += angle(pts[1] - pts[0], pts[0] - pts[n - 1]);
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;
exterior_angle += angle(pts[i] - pts[i - 1], pts[i - 1] - pts[i - 2]);
}
return fabs(exterior_angle - 2 * PI) < eps;
}
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");
}