QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#314476#7730. Convex Checkerlmf_upWA 1ms3660kbC++205.2kb2024-01-25 18:51:422024-01-25 18:51:42

Judging History

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

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

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-8;

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;//大于等于是严格凸包,大于是非严格凸包可以有180°
}

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) {
    int n = (int) a.size (), cnt = 0;
    if (n < 2) return a;
    std::sort(a.begin(), a.end()); // less<pair>
    std::vector <point> ret;
    for (int i = 0; i < n; ++i) {
        while (cnt > 1
               && turn_left (ret[cnt - 2], a[i], ret[cnt - 1]))
            --cnt, ret.pop_back ();
        ++cnt, ret.push_back (a[i]); }
    int fixed = cnt;
    for (int i = n - 2; i >= 0; --i) {
        while (cnt > fixed
               && turn_left (ret[cnt - 2], a[i], ret[cnt - 1]))
            --cnt, ret.pop_back ();
        ++cnt, ret.push_back (a[i]); }
    ret.pop_back (); return ret;
}
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++)
    {
        double 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])
        {
            int flag=1;
            for(int j=0;j<n;j++)
            {
                if(res[(i+j)%n]==tu[j])
                    continue;
                else
                {
                    flag=0;
                    break;
//                    std::cout<<"No\n";
//                    return 0;
                }
            }
            if(flag)
            std::cout<<"Yes\n";
            flag=1;
            std::reverse(tu.begin(),tu.end());
            for(int j=0;j<n;j++)
            {
                if(res[(i+j)%n]==tu[j])
                    continue;
                else
                {
                    flag=0;
                    break;
//                    std::cout<<"No\n";
//                    return 0;
                }
            }
            if(flag)
                std::cout<<"Yes\n";
            else std::cout<<"No\n";
            return 0;
        }
    }
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 0
Wrong Answer
time: 1ms
memory: 3660kb

input:

3
0 0
1 0
0 1

output:

Yes
No

result:

wrong output format Extra information in the output file