QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#238941#7730. Convex CheckeryuxxWA 1ms7912kbC++142.7kb2023-11-04 17:57:062023-11-04 17:57:06

Judging History

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

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

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<t;i++)
    {
        sp[i+t-1]=sp[i];
    }

    
        
    if(n!=t-1)
    {
        // flag=1;
        cout<<"NO";
        return 0;
    }
    // for(int i=1;i<=n;i++)
    // {
    //     cout<<er[i].x<<" "<<er[i].y<<endl;
    // }
    int flag1=0;
    int flag2=0;
    for(int i=1;i<=n+1;i++)
    {
        if(er[1].x==sp[i].x and er[1].y==sp[i].y)
        {
            for(int j=1;j<=n;j++)
            {
               //// cout<<er[j].x<<" "<<er[j].y<<" "<<sp[i+j-1].x<<" "<<sp[i+j-1].y<<endl;
                if(er[j].x!=sp[i+j-1].x or er[j].y!=sp[i+j-1].y)
                {
                    flag1=1;
                   // cout<<j<<" "<<i;
                    break;
                }
            }
            break;
        }
    }
    reverse(er+1,er+n+1);

    for(int i=1;i<=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[i+j-1].x or er[j].y!=sp[i+j-1].y)
                {
                    flag2=1;
                    //cout<<j<<" "<<i;
                    break;
                }
            }
            break;
        }
    }
    if(flag1 and flag2)
    {
        cout<<"No";
    }
    else
    {
        cout<<"Yes";
    }
    

    return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

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

input:

3
0 0
1 0
0 1

output:

Yes

result:

ok answer is YES

Test #2:

score: 0
Accepted
time: 1ms
memory: 5732kb

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: 7844kb

input:

4
0 0
0 3
1 2
1 1

output:

Yes

result:

ok answer is YES

Test #4:

score: 0
Accepted
time: 1ms
memory: 5736kb

input:

3
0 0
0 0
0 0

output:

NO

result:

ok answer is NO

Test #5:

score: 0
Accepted
time: 1ms
memory: 5868kb

input:

5
1 0
4 1
0 1
2 0
3 2

output:

No

result:

ok answer is NO

Test #6:

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

input:

5
0 0
1000000000 0
1000000000 500000000
1000000000 1000000000
0 1000000000

output:

Yes

result:

wrong answer expected NO, found YES