QOJ.ac

QOJ

ID提交记录ID题目HackerOwner结果提交时间测评时间
#726#422540#7730. Convex CheckerQingyuGoatGirl98Success!2024-07-04 19:17:192024-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 CheckerGoatGirl98WA 11ms4792kbC++142.3kb2024-05-27 15:47:072024-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");
}