QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#454894 | #7730. Convex Checker | Nephrenn | WA | 0ms | 3940kb | C++20 | 5.0kb | 2024-06-25 16:17:27 | 2024-06-25 16:17:27 |
Judging History
answer
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> PII;
typedef pair<ll, ll> PLL;
const int MAXN = 1e2 + 10;
const int INF = 0x3f3f3f3f;
const ll INFLL = 0x3f3f3f3f3f3f3f3f;
random_device seed;
mt19937 rnd(seed());
mt19937_64 rnd_64(seed());
const double eps = 1e-9;
int sgn(const double &x) {
return x < -eps ? -1 : (x > eps ? 1 : 0);
}
double sqr(const double &x) {
return x * x;
}
struct Point {
double x, y;
Point operator * (const double &k) {
return {x * k, y * k};
}
Point operator / (const double &k) {
return {x / k, y / k};
}
Point operator + (const Point &a) {
return {x + a.x, y + a.y};
}
Point operator - (const Point &a) {
return {x - a.x, y - a.y};
}
bool operator < (const Point &a) {
// return y == a.y ? x < a.x : y < a.y;
return x == a.x ? y < a.y : x < a.x;
}
};
istream &operator >> (istream &is, Point &p) {
is >> p.x >> p.y;
return is;
}
bool operator < (const Point &a, const Point &b) {
return a.x == b.x ? a.y < b.y : a.x < b.x;
}
bool operator == (const Point &a, const Point &b) {
return a.x == b.x && a.y == b.y;
}
double dis(const Point &a, const Point &b) {
return sqrt(sqr(a.x - b.x) + sqr(a.y - b.y));
}
double det(const Point &a, const Point &b) {
return a.x * b.y - b.x * a.y;
}
double det(const Point &a, const Point &b, const Point &c) {
return (a.x - b.x) * (c.y - b.y) - (a.y - b.y) * (c.x - b.x);
}
double dot(const Point &a, const Point &b) {
return a.x * b.x + a.y * b.y;
}
double dot(const Point &a, const Point &b, const Point &c) {
return (a.x - b.x) * (c.x - b.x) + (a.y - b.y) * (c.y - b.y);
}
struct Line {
Point s, t;
};
bool point_on_segment(Point &a, Line &l) {
return sgn(det(l.s - a, a - l.t)) == 0 && sgn(dot(l.s - a, a - l.t)) >= 0;
}
bool two_side(Point &a, Point &b, Line &c) {
return sgn(det(a - c.s, c.t - c.s)) * sgn(det(b - c.s, c.t - c.s)) < 0;
}
bool inter_judge(Line &a, Line &b) {
if(point_on_segment(b.s, a) || point_on_segment(b.t, a) || point_on_segment(a.s, b) || point_on_segment(a.t, b)) {
return true;
}
return two_side(a.s, a.t, b) && two_side(b.s, b.t, a);
}
Point line_intersect(Line &a, Line &b) {
double u = det(a.t - a.s, b.s - a.s);
double v = -det(a.t - a.s, b.t - a.s);
return (b.s * v + b.t * u) / (v + u);
}
double point_to_line(Point &p, Line &l) {
return abs(det(l.t - l.s, p - l.s)) / dis(l.s, l.t);
}
double point_to_segment(Point &p, Line &l) {
if(sgn(dot(l.s - p, l.t - l.s)) * sgn(dot(l.t - p, l.t - l.s)) <= 0) {
return point_to_line(p, l);
}
return min(dis(p, l.s), dis(p, l.t));
}
double area(vector<Point> &a) {
double res = 0;
for(int i = 0; i < a.size(); ++i) {
int j = (i + 1) % a.size();
res += det(a[i], a[j]);
}
return res / 2.0;
}
bool turn_left(Point &a, Point &b, Point &c) {
return sgn(det(b - a, c - a)) > 0;
}
bool same_dir(Line &a, Line &b) {
return sgn(det(b.t - b.s, a.t - a.s)) == 0 && sgn(dot(b.t - b.s, a.t - a.s)) > 0;
}
vector<Point> convex_hull_Graham(vector<Point> a) {
if(a.size() <= 2) return {}; // 或 return a;
Point base = *min_element(a.begin(), a.end());
sort(a.begin(), a.end(), [&](auto u, auto v) {
int s = sgn(det(u - base, v - base));
if(s) return s > 0;
else return sgn(dis(u, base) - dis(v, base)) < 0;
});
vector<Point> res;
for(auto i : a) {
while(res.size() > 1 && !turn_left(res[res.size() - 2], res[res.size() - 1], i)) {
res.pop_back();
}
res.push_back(i);
}
return res;
}
vector<Point> convex_hull_Andrew(vector<Point> a) {
if(a.size() <= 2) return {}; // 或 return a
sort(a.begin(), a.end());
vector<Point> res;
for(int i = 0; i < a.size(); ++i) {
while(res.size() > 1 && !turn_left(res[res.size() - 2], res[res.size() - 1], a[i])) {
res.pop_back();
}
res.push_back(a[i]);
}
int fix = res.size();
for(int i = a.size() - 2; i >= 0; --i) {
while(res.size() > fix && !turn_left(res[res.size() - 2], res[res.size() - 1], a[i])) {
res.pop_back();
}
res.push_back(a[i]);
}
res.pop_back();
return res;
}
void solve () {
int n;
cin >> n;
vector<Point> p(n);
for(int i = 0; i < n; ++i) cin >> p[i];
p.push_back(p[0]);
p.push_back(p[1]);
for(int i = 0; i < n; ++i) {
int j = i + 1, k = i + 2;
if(sgn(det(p[k] - p[j], p[i] - p[j])) < 0) {
cout << "No\n";
return;
}
}
cout << "Yes\n";
}
int main () {
ios::sync_with_stdio(false);
cin.tie(0); cout.tie(0);
int Task = 1;
// cin >> Task;
while (Task--) {
solve();
}
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 0ms
memory: 3816kb
input:
3 0 0 1 0 0 1
output:
Yes
result:
ok answer is YES
Test #2:
score: -100
Wrong Answer
time: 0ms
memory: 3940kb
input:
4 0 0 0 1 1 1 1 0
output:
No
result:
wrong answer expected YES, found NO