QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#519344#7730. Convex CheckerTJUHuangTaoWA 0ms3756kbC++205.1kb2024-08-14 18:50:552024-08-14 18:50:55

Judging History

你现在查看的是最新测评结果

  • [2024-08-14 18:50:55]
  • 评测
  • 测评结果:WA
  • 用时:0ms
  • 内存:3756kb
  • [2024-08-14 18:50:55]
  • 提交

answer

#include <bits/stdc++.h>
// #define int long long
#define inf 0x3f3f3f3f
#define ll long long
#define pii pair<int, int>
#define tii tuple<int, int, int>
#define db long double
#define all(a) a.begin(), a.end()
using namespace std;
const int maxn = 1e5 + 10;
const int mod = 998244353;
const db eps = 1e-8;       // 根据题目精度要求进行修改
const db PI = acos(-1.0);  // pai, 3.1415916....

int sgn(db x) {  // 进行判断, 提高精度
    if (fabs(x) < eps)
        return 0;           // x == 0, 精度范围内的近似相等
    return x > 0 ? 1 : -1;  // 返回正负
}
typedef struct Point {
    db x, y;
    Point(db x = 0, db y = 0) : x(x), y(y) {}  // 构造函数, 初始值为 0

    // 重载运算符
    // 点 - 点 = 向量(向量AB = B - A)
    Point operator-(const Point& B) const { return Point(x - B.x, y - B.y); }

    // 点 + 点 = 点, 点 + 向量 = 向量, 向量 + 向量 = 向量
    Point operator+(const Point& B) const { return Point(x + B.x, y + B.y); }

    // 向量 × 向量 (叉积)
    db operator^(const Point& B) const { return x * B.y - y * B.x; }

    // 向量 · 向量 (点积)
    db operator*(const Point& B) const { return x * B.x + y * B.y; }

    // 点 * 数 = 点, 向量 * 数 = 向量
    Point operator*(const db& B) const { return Point(x * B, y * B); }

    // 点 / 数 = 点, 向量 / 数 = 向量
    Point operator/(const db& B) const { return Point(x / B, y / B); }

    // 判断大小, 一般用于排序
    bool operator<(const Point& B) const {
        return x < B.x || (x == B.x && y < B.y);
    }

    // 判断相等, 点 == 点, 向量 == 向量, 一般用于判断和去重
    bool operator==(const Point& B) const {
        return sgn(x - B.x) == 0 && sgn(y - B.y) == 0;
    }

    // 判断不相等, 点 != 点, 向量 != 向量
    bool operator!=(const Point& B) const {
        return sgn(x - B.x) || sgn(y - B.y);
    }
} Vector;
using Points = vector<Point>;
// 判断点在直线的哪边
// Need: (-, ^), sgn()
// 点在直线上, 返回 0 (三点共线)
// 点在直线的逆时针方向, 返回 1
// 点在直线的顺时针方向, 返回 -1
// 点 a, b (向量ab) 所在的直线和点 c
// 使用的时候要注意 a 和 b 的顺序, 有时顺序不同, 结果不同
int Cross(Point a, Point b, Point c) {
    return sgn((b - a) ^ (c - a));
}
// 判断多边形poly是否是凸多边形(前提是多边形)
// Need: Cross
struct Line {
    Point s, e;
    Line() {}
    Line(Point x, Point y) : s(x), e(y) {}
};
struct Seg {
    Point s, e;
    Seg() {}
    Seg(Point x, Point y) : s(x), e(y) {}
};
bool IsConvex(Points poly) {
    int n = poly.size();
    if (n < 3)
        return false;
    Line side = {poly[0], poly[1]};
    // double rel = Cross(side.s, side.e, poly[2]);
    int f1 = 1, f2 = 1;
    for (int i = 0; i < n; i++) {
        side.s = poly[i];
        side.e = poly[(i + 1) % n];
        if (Cross(side.s, side.e, poly[(i + 2) % n]) == -1)
            f1 = 0;
        if (Cross(side.s, side.e, poly[(i + 2) % n]) == 1)
            f2 = 0;
    }
    return f1 | f2;
}
bool le(db a, db b) {
    return a - b < eps;
}  // <=
using Points = vector<Point>;
bool check(Point p, Point q, Point r) {
    return le(0, (q - p) ^ (r - q));
}
vector<Point> Andrew(Points poly) {  // 末尾额外塞了个头
    int n = poly.size(), top = 0;
    vector<int> stk(n + 2, 0), used(n + 2, 0);
    sort(poly.begin(), poly.end());
    stk[++top] = 0;
    for (int i = 1; i < n; i++) {
        while (top > 1 &&
               sgn((poly[stk[top]] - poly[stk[top - 1]]) ^
                   (poly[i] - poly[stk[top]])) <= 0)  // 去掉等号可以找共线的点
            used[stk[top--]] = 0;

        used[i] = 1;
        stk[++top] = i;
    }
    int tmp = top;
    for (int i = n - 2; i >= 0; i--) {
        if (used[i])
            continue;
        while (top > tmp && sgn((poly[stk[top]] - poly[stk[top - 1]]) ^
                                (poly[i] - poly[stk[top]])) <= 0)
            used[stk[top--]] = 0;

        used[i] = 1;
        stk[++top] = i;
    }
    vector<Point> a;
    for (int i = 1; i <= top; i++)
        a.push_back(poly[stk[i]]);
    return a;
}
db convex_polygon_area(Points p) {
    db area = 0;
    int n = p.size();
    for (int i = 1; i <= n - 2; ++i)
        area += (p[i] - p[0]) ^ (p[i + 1] - p[0]);
    // return area / 2;
    return area / 2;  // 不加的话求的是有向面积,逆时针为负,顺时针为正
}
signed main() {
    // freopen("2.in", "r", stdin);
    // freopen("2.out", "w", stdout);
    ios::sync_with_stdio(false);
    cin.tie(0), cout.tie(0);
    int n;
    cin >> n;
    Points poly;
    int flag = 1;
    for (int i = 1; i <= n; i++) {
        Point p;
        cin >> p.x >> p.y;
        poly.push_back(p);
    }
    Points tubao = Andrew(poly);
    tubao.pop_back();
    if (tubao.size() == n && IsConvex(tubao) &&
        convex_polygon_area(poly) == convex_polygon_area(tubao))
        cout << "Yes\n";
    else
        cout << "No\n";
    return 0;
}

詳細信息

Test #1:

score: 100
Accepted
time: 0ms
memory: 3748kb

input:

3
0 0
1 0
0 1

output:

Yes

result:

ok answer is YES

Test #2:

score: -100
Wrong Answer
time: 0ms
memory: 3756kb

input:

4
0 0
0 1
1 1
1 0

output:

No

result:

wrong answer expected YES, found NO