QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#238868#7730. Convex CheckeryuxxWA 0ms7676kbC++142.4kb2023-11-04 17:46:252023-11-04 17:46:26

Judging History

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

  • [2024-07-04 19:27:17]
  • hack成功,自动添加数据
  • (/hack/727)
  • [2024-07-04 19:17:30]
  • hack成功,自动添加数据
  • (/hack/726)
  • [2023-11-04 17:46:26]
  • 评测
  • 测评结果:WA
  • 用时:0ms
  • 内存:7676kb
  • [2023-11-04 17:46:25]
  • 提交

answer

#include <bits/stdc++.h>
using namespace std;
const int N=1e5+5;
const double eps=1e-7;
int n;
struct point {
    double x, y;
    point () {}
    point (double a, double b) : x (a), y (b) {}
    bool operator<(const point &a)const{
        if(a.x==x)
        {
            return a.y>y;
        }
        return a.x>x;
    }
    point operator - (const point &b) {
        return point (x - b.x, y - b.y);
    }
};
point p[N], sp[N];
point er[N];
int cmp (double x) {
    if (fabs (x) < eps) return 0;
    return x > 0 ? 1 : -1;
}
double dis (point a, point b) {
    return sqrt((a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y));
}
double cp (point a, point b) {
    return a.x * b.y - a.y * b.x;
}
int Andrew () {
    sort(p+1,p+n+1);
    int len=0;
    for (int i=1;i<=n;i++){
        while(len>1&&cmp(cp(sp[len]-sp[len-1],p[i]-sp[len-1]))<0) 
        {
            len--;
        }    
        sp[++len]=p[i];
    }
    int k=len;
    for(int i=n-1;i>=1;i--)
    {
        while(len>k&&cmp(cp(sp[len]-sp[len-1],p[i]-sp[len-1]))<0)
        {   
            len--;
        }
        sp[++len]=p[i];
    }
    return len;
}

int main() 
{
    ios::sync_with_stdio(false);
    cin.tie(0);cout.tie(0);

        cin>>n;
        for(int i=1;i<=n;i++)
        {
            cin>>p[i].x>>p[i].y;
            er[i]=p[i];
        }


        int t=Andrew();
        reverse(er+1,er+n+1);
        // for(int i=1;i<=n;i++)
        // {
        //     cout<<er[i].x<<" "<<er[i].y<<endl;
        // }
        // cout<<t-1<<endl;
        // for(int i=1;i<t;i++)
        // {
        //     printf("%.0lf %.0lf\n",sp[i].x,sp[i].y);
        // }
        for(int i=1;i<t;i++)
        {
            sp[i+t-1]=sp[i];
        }

        int flag=0;
        // cout<<t;
        if(n!=t-1)
        {
            flag=1;
        }
        // cout<<flag;
        for(int i=1;i<=2*t-2-n+1;i++)
        {
            if(er[1].x==sp[i].x and er[1].y==sp[i].y)
            {
                for(int j=1;j<=n;j++)
                {
                    if(er[j].x!=sp[j+i-1].x or er[j].y!=sp[j+i-1].y)
                    {
                        flag=1;
                        break;
                    }
                }
                break;
            }
        }
        if(flag)
        {
            cout<<"No";
        }
        else
        {
            cout<<"Yes";
        }
    

    return 0;
}

詳細信息

Test #1:

score: 0
Wrong Answer
time: 0ms
memory: 7676kb

input:

3
0 0
1 0
0 1

output:

No

result:

wrong answer expected YES, found NO