QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#314464#7730. Convex Checkerlmf_upWA 0ms3904kbC++204.9kb2024-01-25 18:34:282024-01-25 18:34:29

Judging History

你现在查看的是最新测评结果

  • [2024-07-04 19:27:17]
  • hack成功,自动添加数据
  • (/hack/727)
  • [2024-07-04 19:17:30]
  • hack成功,自动添加数据
  • (/hack/726)
  • [2024-01-25 18:34:29]
  • 评测
  • 测评结果:WA
  • 用时:0ms
  • 内存:3904kb
  • [2024-01-25 18:34:28]
  • 提交

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