QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#537854 | #7730. Convex Checker | 0x3ea | WA | 0ms | 3948kb | C++17 | 3.1kb | 2024-08-30 19:06:59 | 2024-08-30 19:06:59 |
Judging History
answer
#include <bits/stdc++.h>
#define endl '\n'
#define Vector Point
using namespace std;
using ll = long long;
using db = double;
using pii = pair<int, int>;
using pll = pair<ll, ll>;
const int N = 5e3 + 10;
const int mod = 998244353;
ll sign(ll a) { return a < 0 ? -1 : a > 0; }
struct Point
{
db x, y;
Point() {}
Point(db x, db y) : x(x), y(y) {}
Point operator+(Point p) { return {x + p.x, y + p.y}; }
Point operator-(Point p) { return {x - p.x, y - p.y}; }
Point operator*(db d) { return {x * d, y * d}; }
Point operator/(db d) { return {x / d, y / d}; }
bool operator==(Point &p) const { return !sign(x - p.x) && !sign(y - p.y); }
int toleft(Point b)
{ // 点在线段的方向
ll res = x * b.y - y * b.x;
if (res == 0)
return 0; // 直线上
else if (res > 0)
return 1; // 左
return -1; // 右
}
friend istream &operator>>(istream &is, Point &p)
{
return is >> p.x >> p.y;
}
friend ostream &operator<<(ostream &os, Point p)
{
return os << "(" << p.x << ", " << p.y << ")";
}
};
bool operator<(const Point &p1, const Point &p2)
{
if (p1.x == p2.x)
return p1.y < p2.y;
return p1.x < p2.x;
}
db dot(Point a, Point b)
{
return a.x * b.x + a.y * b.y;
}
db cross(Point a, Point b)
{
return a.x * b.y - a.y * b.x;
}
db dis1(Point a, Point b)
{ // 两点距离的平方
return sqrt((a.x - b.x) * (a.x - b.x) + (a.y - b.y) * (a.y - b.y));
// return sqrtl((a.x - b.x) * (a.x - b.x) + (a.y - b.y) * (a.y - b.y));//long double ver
}
db dis2(Point a, Point b)
{ // 两点距离的平方
return (a.x - b.x) * (a.x - b.x) + (a.y - b.y) * (a.y - b.y);
}
bool ver(Vector a, Vector b)
{ // 是否垂直
return sign(dot(a, b)) == 0;
}
vector<Point> Andrew(vector<Point> &s)
{
sort(s.begin(), s.end());
int tp = 0;
vector<int> stk(s.size() + 10, 0);
stk[++tp] = 0;
vector<bool> used(s.size() + 1, 0);
for (int i = 1; i < s.size(); i++)
{
while (tp >= 2 && cross(s[stk[tp]] - s[stk[tp - 1]], s[i] - s[stk[tp]]) <= 0)
used[stk[tp--]] = 0;
used[i] = 1;
stk[++tp] = i;
}
int sz = tp;
for (int i = (int)s.size() - 2; i >= 0; i--)
{
if (used[i])
continue;
while (tp > sz && cross(s[stk[tp]] - s[stk[tp - 1]], s[i] - s[stk[tp]]) <= 0)
used[stk[tp--]] = 0;
used[i] = 1;
stk[++tp] = i;
}
vector<Point> ans;
for (int i = 1; i < tp; i++)
ans.push_back(s[stk[i]]);
return ans;
}
void solve()
{
int n;
cin >> n;
vector<Point> a(n);
for (auto &i : a)
cin >> i;
auto res = Andrew(a);
// for (auto i : res)
// cout << i << endl;
cout << (res.size() == n ? "Yes" : "No") << endl;
}
int main()
{
#ifdef x3ea
freopen("in.txt", "r", stdin);
freopen("out.txt", "w", stdout);
#endif
ios::sync_with_stdio(false);
cin.tie(0), cout.tie(0);
int _ = 1;
// cin >> _;
for (; _; _--)
solve();
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 0ms
memory: 3716kb
input:
3 0 0 1 0 0 1
output:
Yes
result:
ok answer is YES
Test #2:
score: 0
Accepted
time: 0ms
memory: 3716kb
input:
4 0 0 0 1 1 1 1 0
output:
Yes
result:
ok answer is YES
Test #3:
score: 0
Accepted
time: 0ms
memory: 3716kb
input:
4 0 0 0 3 1 2 1 1
output:
Yes
result:
ok answer is YES
Test #4:
score: 0
Accepted
time: 0ms
memory: 3916kb
input:
3 0 0 0 0 0 0
output:
No
result:
ok answer is NO
Test #5:
score: -100
Wrong Answer
time: 0ms
memory: 3948kb
input:
5 1 0 4 1 0 1 2 0 3 2
output:
Yes
result:
wrong answer expected NO, found YES