QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#313189 | #7730. Convex Checker | supepapupu | WA | 1ms | 4240kb | C++17 | 2.5kb | 2024-01-24 16:30:13 | 2024-01-24 16:30:13 |
Judging History
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