QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#373237 | #7730. Convex Checker | dodola | WA | 1ms | 3944kb | C++14 | 3.8kb | 2024-04-01 11:55:57 | 2024-04-01 11:56:04 |
Judging History
answer
#include<bits/stdc++.h>
using namespace std;
typedef unsigned long long ull;
typedef long long ll;
typedef double ld;
const ld eps = 1e-18;
const ld pi = acos(-1.0);
/*
符合洛谷题目格式的代码
*/
struct point {
ld x, y;
point operator+(const point& p)const {
return { x + p.x,y + p.y };
}
point operator-(const point& p)const {
return { x - p.x,y - p.y };
}
bool operator==(const point& p)const {
return p.x == x && p.y == y;
}
bool operator!=(const point& p)const {
return p.x != x || p.y != y;
}
point rotate(ld t)const {
return { x * cos(t) - y * sin(t), x * sin(t) + y * cos(t) };
}
point rot90()const {
return { -y,x };
}
};
struct line {
point s, t;
};
int sgn(ld x) {
if (fabs(x) < eps) return 0;
return x < 0 ? -1 : 1;
}
ld sqr(ld x) {
return x * x;
}
ld dis(const point& a, const point& b) {
return sqrt(sqr(a.x - b.x) + sqr(a.y - b.y));
}
ld dot(const point& a, const point& b) {
return a.x * b.x + a.y * b.y;
}
ld det(const point& a, const point& b) {
return a.x * b.y - a.y * b.x;
}
vector<point>Andrew(vector<point>& p) {
sort(p.begin(), p.end(), [](const point& a, const point& b) {
return a.x == b.x ? a.y < b.y : a.x < b.x;
});
vector<point> res;
for (int i = 0; i < p.size(); i++) { // 下凸壳
while (res.size() > 1
&& det(res.back() - res[res.size() - 2], p[i] - res[res.size() - 2]) <= 0)
res.pop_back();
res.push_back(p[i]);
}
int k = res.size();
for (int i = p.size() - 2; i >= 0; i--) { // 上凸壳
while (res.size() > k
&& det(res.back() - res[res.size() - 2], p[i] - res[res.size() - 2]) <= 0)
res.pop_back();
res.push_back(p[i]);
}
res.pop_back(); // 删除重复的点,即首尾相同
return res;
}
bool turn_left(const point& a, const point& b, const point& c) {
return sgn(det(b - a, c - a)) > 0;
}
vector<point> Graham(vector<point>& p) {
point base = *min_element(p.begin(), p.end(), [](const point& a, const point& b) {
return a.y == b.y ? a.x < b.x : a.y < b.y;
});
sort(p.begin(), p.end(), [&](const point& u, const point& v) {
int s = sgn(det(u - base, v - base));
if (s)return s > 0;
return sgn(dis(u, base) - dis(v, base)) < 0;
});
vector<point>res;
for (auto i : p) {
while (res.size() > 1
&& !turn_left(res[res.size() - 2], res.back(), i))
res.pop_back();
res.push_back(i);
}
return res;
}
// 求凸包的周长
ld convex_perimeter(vector<point>& p) {
ld res = 0;
for (int i = 0; i < p.size(); i++)
res += dis(p[i], p[(i + 1) % p.size()]);
return res;
}
bool convex_checker(vector<point> p) {
vector<point> res = Andrew(p);
if (res.size() != p.size())return false;
if (res.size() < 3)return false;
while (p.size() && p.front() != res.front()) {
res.push_back(res.front());
res.erase(res.begin());
}
if (p[1] != res[1]) {
reverse(res.begin(), res.end());
res.insert(res.begin(), res.back());
res.pop_back();
}
for (int i = 0; i < p.size(); i++) {
// cout << p[i].x << " " << p[i].y << endl;
// cout << res[i].x << " " << res[i].y << endl;
if (p[i] != res[i])return false;
}
return true;
}
void solve() {
ll n;cin >> n;
vector<point> p(n);
for (ll i = 0;i < n;i++) {
cin >> p[i].x >> p[i].y;
}
if (convex_checker(p)) {
cout << "Yes" << endl;
}
else {
cout << "No" << endl;
}
}
int main() {
solve();
return 0;
}
详细
Test #1:
score: 100
Accepted
time: 1ms
memory: 3944kb
input:
3 0 0 1 0 0 1
output:
Yes
result:
ok answer is YES
Test #2:
score: -100
Wrong Answer
time: 0ms
memory: 3724kb
input:
4 0 0 0 1 1 1 1 0
output:
No
result:
wrong answer expected YES, found NO