QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#238801#7730. Convex CheckeryuxxWA 0ms3956kbC++142.2kb2023-11-04 17:35:162023-11-04 17:35:17

Judging History

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

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

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];
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);
    int t;
    t=1;
    // cin>>t;
    while(t--)
    {
        cin>>n;
        char c;
        for(int i=1;i<=n;i++)
        {
            cin>>p[i].x>>p[i].y;
        }
        int t=Andrew();
        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];
    }
    reverse(p+1,p+n+1);
    int flag=0;
    if(n!=t-1)
    {
        flag=1;
    }

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

Details

Tip: Click on the bar to expand more detailed information

Test #1:

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

input:

3
0 0
1 0
0 1

output:

3
No0 0
1 0
0 1

result:

wrong output format YES or NO expected, but 3 found