QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#519344 | #7730. Convex Checker | TJUHuangTao | WA | 0ms | 3756kb | C++20 | 5.1kb | 2024-08-14 18:50:55 | 2024-08-14 18:50:55 |
Judging History
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;
}
Details
Tip: Click on the bar to expand more detailed information
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