QOJ.ac
QOJ
ID | Submission ID | Problem | Hacker | Owner | Result | Submit time | Judge time |
---|---|---|---|---|---|---|---|
#550 | #343612 | #7730. Convex Checker | 5ab | 5ab | Failed. | 2024-03-02 20:58:14 | 2024-03-02 20:58:14 |
Details
Extra Test:
Accepted
time: 1ms
memory: 3604kb
input:
7 3 2 3 5 5 3 4 3 4 3 1 4 5 5
output:
No
result:
ok answer is NO
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#343612 | #7730. Convex Checker | 5ab | AC ✓ | 33ms | 7300kb | C++20 | 2.0kb | 2024-03-02 20:13:13 | 2024-07-04 19:27:58 |
answer
/* name: 7730
* author: 5ab
* created at: 2024-03-02
*/
#include <bits/stdc++.h>
using namespace std;
#define all(x) (x).begin(), (x).end()
#define ssz(x) (int((x).size()))
auto chmax = [](auto& x, auto y) { if (x < y) x = y; };
auto chmin = [](auto& x, auto y) { if (y < x) x = y; };
using ll = long long;
const int N = 2e5;
struct point
{
int x, y;
point operator-(const point& q) const {
return { x - q.x, y - q.y };
}
bool operator==(const point& q) const {
return x == q.x && y == q.y;
}
}
a[N], b[N];
inline ll cross(const point& p, const point& q) {
return 1ll * p.x * q.y - 1ll * q.x * p.y;
}
inline ll dot(const point& p, const point& q) {
return 1ll * p.x * q.x + 1ll * p.y * q.y;
}
signed main()
{
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
int n;
cin >> n;
for (int i = 0; i < n; i++)
cin >> a[i].x >> a[i].y;
copy(a, a + n, b);
swap(b[0], *min_element(b, b + n, [](auto& p, auto& q) {
return p.x == q.x ? p.y < q.y : p.x < q.x;
}));
sort(b + 1, b + n, [&](auto& p, auto& q) {
ll t = cross(p - b[0], q - b[0]);
return t ? t > 0 : dot(q - p, p - b[0]) > 0;
});
int lm = unique(b, b + n) - b;
vector<point> cv;
for (int i = 0; i < lm; i++)
{
while (ssz(cv) > 1 && cross(b[i] - cv.back(), cv.back() - end(cv)[-2]) >= 0)
cv.pop_back();
// cerr << b[i].x << " " << b[i].y << endl;
cv.push_back(b[i]);
}
// cerr << ssz(cv) << " " << lm << endl;
if (ssz(cv) != n)
{
cout << "No\n";
return 0;
}
auto check = [&]() -> bool
{
int sp = find(a, a + n, cv[0]) - a;
// cerr << sp << endl;
if (sp == n)
return 0;
for (int i = 0, j = sp; i < n; i++, j = (j + 1) % n)
if (a[j] != cv[i])
{
// cerr << i << " " << j << " " << cv[i].x << " " << cv[i].y << endl;
return 0;
}
return 1;
};
bool res = check();
reverse(all(cv));
cout << ((check() || res) ? "Yes" : "No") << "\n";
return 0;
}
// started coding at: 03-02 19:14:06