QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#313189#7730. Convex CheckersupepapupuWA 1ms4240kbC++172.5kb2024-01-24 16:30:132024-01-24 16:30:13

Judging History

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

  • [2024-07-04 19:27:17]
  • hack成功,自动添加数据
  • (/hack/727)
  • [2024-07-04 19:17:30]
  • hack成功,自动添加数据
  • (/hack/726)
  • [2024-01-24 16:30:13]
  • 评测
  • 测评结果:WA
  • 用时:1ms
  • 内存:4240kb
  • [2024-01-24 16:30:13]
  • 提交

answer

#include <bits/stdc++.h>

#define x first
#define y second
#define el '\n'
#define debug(x) cerr << #x << ": " << x << endl
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef pair<double, double> pdd;
const int N = 3e5 + 10, INF = 0x3f3f3f3f, mod = 998244353;

const double eps = 1e-8;
const double pi = acos(-1);

pdd operator+ (const pdd &a, const pdd &b) {
    return {a.x + b.x, a.y + b.y};
}

pdd operator- (const pdd &a, const pdd &b) {
    return {a.x - b.x, a.y - b.y};
}

pdd operator* (const pdd &a, const double &b) {
    return {a.x * b, a.y * b};
}

pdd operator/ (const pdd &a, const double &b) {
    return {a.x / b, a.y / b};
}

double operator* (const pdd &a, const pdd &b) {
    return a.x * b.x + a.y * b.y;
}

double operator^ (const pdd &a, const pdd &b) {
    return a.x * b.y - a.y * b.x;
}

struct Line {
    pdd st, ed;
};

struct Circle {
    pdd p;
    double r;
};

int sign(const double &a) {
    if (fabs(a) < eps) return 0;
    if (a > 0) return 1;
    return -1;
}

int dcmp(const double &a, const double &b) {
    if (fabs(a - b) < eps) return 0;
    if (a > b) return 1;
    return -1;
}

double area(const pdd &a, const pdd &b, const pdd &c) {
    return (b - a) ^ (c - a);
}

double get_dis(const pdd &a, const pdd &b) {
    return hypot(a.x - b.x, a.y - b.y);
}

// 直线夹角
double get_angle(const Line &a) {
    if (a.ed.y == a.st.y) return 0;
    return atan2(a.ed.y - a.st.y, a.ed.x - a.st.x);
}

// 两直线夹角
double get_angle(const Line &a, const Line &b) {
    // cout << get_angle(a) << ' ' << get_angle(b) << el;
    return get_angle(a) - get_angle(b);
}

bool convex(vector<pdd> &q) {
    int n = q.size();
    auto check = [&]() -> bool {
        double s = 0;
        for (int i = 0; i < n; ++i) {
            if (!dcmp(q[i].x, q[(i + 1) % n].x) && !dcmp(q[i].y, q[(i + 1) % n].y)) return 0;
            if (sign(area(q[(i + 1) % n], q[i], q[(i + 2) % n])) <= 0) return 0;
            s += abs(get_angle((Line){q[(i + 1) % n], q[i]}, (Line){q[(i + 1) % n], q[(i + 2) % n]}));
        }
        // debug(s);
        return abs(s / pi - n + 2) <= 0.5;
    };
    if (check()) return 1;
    reverse(q.begin(), q.end());
    return check();
}

int main() {
    ios::sync_with_stdio(0); cin.tie(0);
    int n; cin >> n;
    vector<pdd> q(n);
    for (int i = 0; i < n; ++i) cin >> q[i].x >> q[i].y;
    cout << (convex(q) ? "Yes" : "No");
}

详细

Test #1:

score: 100
Accepted
time: 1ms
memory: 4240kb

input:

3
0 0
1 0
0 1

output:

Yes

result:

ok answer is YES

Test #2:

score: 0
Accepted
time: 1ms
memory: 3924kb

input:

4
0 0
0 1
1 1
1 0

output:

Yes

result:

ok answer is YES

Test #3:

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

input:

4
0 0
0 3
1 2
1 1

output:

No

result:

wrong answer expected YES, found NO