QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#314468#7730. Convex Checkerlmf_upWA 1ms3616kbC++204.6kb2024-01-25 18:42:262024-01-25 18:42:28

Judging History

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

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

answer

#include<bits/stdc++.h>
#define cp const point &
#define cl const line &
#define cc const circle
#define LD long long
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 a.x==b.x&&(a.y==b.y);
//    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) {
    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++)
    {
        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;
        }
    }
}

詳細信息

Test #1:

score: 100
Accepted
time: 1ms
memory: 3604kb

input:

3
0 0
1 0
0 1

output:

Yes

result:

ok answer is YES

Test #2:

score: -100
Wrong Answer
time: 0ms
memory: 3616kb

input:

4
0 0
0 1
1 1
1 0

output:

No

result:

wrong answer expected YES, found NO