QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#314464 | #7730. Convex Checker | lmf_up | WA | 0ms | 3904kb | C++20 | 4.9kb | 2024-01-25 18:34:28 | 2024-01-25 18:34:29 |
Judging History
answer
#include<bits/stdc++.h>
#define cp const point &
#define cl const line &
#define cc const circle
#define LD long double
const LD eps = 1e-10;
int sgn(LD x)
{
return x > eps ? 1 : (x < -eps ? -1 : 0);
}
LD sqr(LD x)
{ return x * x; }
struct point
{
LD x, y;
point operator+(cp a) const
{ return {x + a.x, y + a.y}; }
point operator-(cp a) const
{ return {x - a.x, y - a.y}; }
point operator*(LD t) const
{ return {x * t, y * t}; }
point operator/(LD t) const
{ return {x / t, y / t}; }
point rot(LD t) const
{ return {x * cos(t) - y * sin(t), x * sin(t) + y * cos(t)}; }
point rot90() const
{ return {-y, x}; }
double len2() const
{ return x * x + y * y; }
double len() const
{ return sqrt(x * x + y * y); }
point unit() const
{
double d = len();
return {x / d, y / d};
}
friend bool operator<(cp a, cp b)
{
if (a.x != b.x)
return a.x < b.x;
else return a.y < b.y;
}
};
LD dot(cp a, cp b);
bool operator==(cp a, cp b)
{
return sgn(dot(a - b, a - b));
}
LD dis(cp a, cp b)
{
return sqrtl(sqr(a.x - b.x) + sqr(a.y - b.y));
}
LD dot(cp a, cp b)
{
return a.x * b.x + a.y * b.y;
}
LD det(cp a, cp b)
{
return a.x * b.y - b.x * a.y;
}
bool turn_left(cp a, cp b, cp c)
{
return sgn(det(b - a, c - a)) >= 0;
}
struct line
{
point s, t;
line(point a, point b) : s(a), t(b)
{}
};
bool same_dir(cl a, cl b)
{
return sgn(det(b.t - b.s, a.t - a.s)) == 0 && sgn(dot(b.t - b.s, a.t - a.s)) > 0;
}
bool point_on_segment(cp a, cl l)//前一句是点在直线上
{
return sgn(det(l.s - a, a - l.t)) == 0 && sgn(dot(l.s - a, a - l.t)) <= 0;
}
bool two_side(cp a, cp b, cl c)
{
return sgn(det(a - c.s, c.t - c.s)) * sgn(det(b - c.s, c.t - c.s)) < 0;
}
bool intersect_judge(cl a, cl b)
{
if (point_on_segment(a.s, b) || point_on_segment(a.t, b) || point_on_segment(b.s, a) ||
point_on_segment(b.t, a))
return true;
return two_side(a.s, a.t, b) && two_side(b.s, b.t, a);
}
point line_intersect(cl a, cl b)
{
double s1 = det(a.t - a.s, b.s - a.s);
double s2 = det(a.t - a.s, b.t - a.s);
return (b.s * s2 - b.t * s1) / (s2 - s1);
}
bool point_on_ray(cp a, cl b)
{
return sgn(det(a - b.s, b.t - b.s)) == 0 && sgn(dot(a - b.s, b.t - b.s)) >= 0;
}
bool ray_intersect_judge(line a, line b)
{
double s1, s2;
s1 = det(a.t - a.s, b.s - a.s);
s2 = det(a.t - a.s, b.t - a.s);
if (sgn(s1) == 0 && sgn(s2) == 0)
return sgn(dot(a.t - a.s, b.s - a.s)) >= 0 || sgn(dot(b.t - b.s, a.s - b.s));
if (!sgn(s1 - s2) || sgn(s1) == sgn(s2 - s1))return 0;
std::swap(a, b);
s1 = det(a.t - a.s, b.s - a.s);
s2 = det(a.t - a.s, b.t - a.s);
return sgn(s1) != sgn(s2 - s1);
}
LD point_to_line(cp a, cl b)
{
return abs(det(b.t - b.s, a - b.s)) / dis(b.s, b.t);
}
point project_to_line(cp a, cl b)
{
return b.s + (b.t - b.s) * (dot(a - b.s, b.t - b.s) / (b.t - b.s).len2());
}
LD point_to_segment(cp a, cl b)
{
if (sgn(dot(b.s - a, b.t - b.s)) * sgn(dot(b.t - a, b.t - b.s)) <= 0)
return abs(det(b.t - b.s, a - b.s)) / dis(b.s, b.t);
return std::min(dis(a, b.s), dis(a, b.t));
}
std::vector<point> convex_hull(std::vector<point> a)
{
if (a.size() <= 2) return a; //或 者 return {};
point base = *min_element(a.begin(), a.end()); //字 典 序: less <pair >
std::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;
});
std::vector<point> ret;
for (auto i: a)
{
while (ret.size() > 1
&& !turn_left(ret[ret.size() - 2], ret[ret.size() - 1], i))
ret.pop_back();
ret.push_back(i);
}
return ret; //或 者 在 ret.size() <= 2 时 return {};
}
int main()
{
std::ios::sync_with_stdio(false);
std::cin.tie(0), std::cout.tie(0);
std::cout << std::fixed << std::setprecision(2);
int n;
std::cin >> n;
std::vector<point> tu;
for (int i = 1; i <= n; i++)
{
LD x, y;
std::cin >> x >> y;
tu.push_back({x, y});
}
auto res = convex_hull(tu);
if (res.size() != n)
{
std::cout << "No\n";
return 0;
}
for (int i = 0; i < n; i++)
{
if (res[i] == tu[0])
{
for (int j = 0; j < n; j++)
{
if (res[(i + j) % n] == tu[j])
continue;
else
{
std::cout << "No\n";
return 0;
}
}
std::cout << "Yes\n";
return 0;
}
}
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 0ms
memory: 3904kb
input:
3 0 0 1 0 0 1
output:
Yes
result:
ok answer is YES
Test #2:
score: 0
Accepted
time: 0ms
memory: 3724kb
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: 3660kb
input:
4 0 0 0 3 1 2 1 1
output:
Yes
result:
ok answer is YES
Test #4:
score: -100
Wrong Answer
time: 0ms
memory: 3728kb
input:
3 0 0 0 0 0 0
output:
result:
wrong output format Unexpected end of file - token expected