QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#313115#7730. Convex CheckerzjjwsWA 1ms3556kbC++145.8kb2024-01-24 16:09:152024-01-24 16:09:15

Judging History

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

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

answer

#include <map>
#include <set>
#include <cmath>
#include <queue>
#include <vector>
#include <string>
#include <time.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <iostream>
#include <algorithm>
#define LL long long
using namespace std;
bool ifnum(char x){return x>='0'&&x<='9';}
bool ifupchr(char x){return x>='A'&&x<='Z';}
bool iflochr(char x){return x>='a'&&x<='z';}
struct Rin
{
    char c;
    char gc()
    {
        return getchar();
    }
    Rin&operator >>(int &x)
    {
        bool tag=false;x=0;
        for(c=gc();c>'9'||c<'0';c=gc())if(c=='-'){c=gc();tag=true;break;}
        for(;c>='0'&&c<='9';c=gc())x=(x<<1)+(x<<3)+(c^'0');if(tag)x=-x;return *this;
    }
    Rin&operator >>(LL &x)
    {
        bool tag=false;x=0;
        for(c=gc();c>'9'||c<'0';c=gc())if(c=='-'){c=gc();tag=true;break;}
        for(;c>='0'&&c<='9';c=gc())x=(x<<1)+(x<<3)+(c^'0');if(tag)x=-x;return *this;
    }
    Rin&operator >>(char &x)
    {
        for(c=gc();!ifnum(c)&&!iflochr(c)&&!ifupchr(c);c=gc());
        x=c;
        return *this;
    }
    Rin&operator >>(string &x)
    {
        x.clear();
        for(c=gc();!ifnum(c)&&!iflochr(c)&&!ifupchr(c);c=gc());
        for(;ifnum(c)||iflochr(c)||ifupchr(c);c=gc())x.push_back(c);
        return *this;
    }
}rin;
#define rin(x) rin>>x
void jh(int &x,int &y){if(x^y)x^=y^=x^=y;return;}
void jh(LL &x,LL &y){if(x^y)x^=y^=x^=y;return;}
int min(int x,int y){return x<y?x:y;}
int max(int x,int y){return x>y?x:y;}
LL min(LL x,LL y){return x<y?x:y;}
LL max(LL x,LL y){return x>y?x:y;}
const double eps=1e-10;
const double PI=acos(-1.0);
double sgn(double x){return (x>eps)-(x<-eps);}

struct PT
{
    double x,y;
    PT(){x=0;y=0;}
    PT(double x,double y):x(x),y(y){}
    PT operator -(const PT &a)const {return PT(x-a.x,y-a.y);}
    PT operator +(const PT &a)const {return PT(x+a.x,y+a.y);}
    PT operator *(const double a)const {return PT(x*a,y*a);}
    friend PT operator *(const double &a,const PT &b){return PT(a*b.x,a*b.y);}
    PT operator /(const double a)const {return PT(x/a,y/a);}
    bool operator ==(const PT &a){return sgn(x-a.x)==0&&sgn(y-a.y)==0;}
    bool operator !=(const PT &a){return !(*this==a);}
    PT perp(){return PT(-y,x);}
    double arg(){return atan2(y,x);}
    double norm(){return sqrt(x*x+y*y);}
    double norm2(){return x*x+y*y;}
    PT truncate(double r)
    {
        double k=norm();
        if(sgn(k)==0)return *this;
        r/=k;
        return PT(x*r,y*r);
    }
};
struct Line
{
    PT s,t;
    Line(){s=PT(0,0),t=PT(0,0);}
    Line(PT x,PT y):s(x),t(y){}
};
double dot(PT a,PT b){return a.x*b.x+a.y*b.y;}
double det(PT a,PT b){return a.x*b.y-a.y*b.x;}
int turn_l_or_r(Line l,PT x)
{
    double v=det(l.t-l.s,x-l.s);
    return sgn(v);//1 为左侧(逆时针)0 为线上
}

double Edis(PT a,PT b){return sqrt((a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y));}
double Edis2(PT a,PT b){return (a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y);}

PT perp(PT a) { return PT(-a.y, a.x); }
PT rotatel90(PT a) { return PT(-a.y, a.x); }
PT rotater90(PT a) { return PT(a.y, -a.x); }
PT rotatel(PT a, double t) {return PT(a.x*cos(t)-a.y*sin(t),a.x*sin(t)+a.y*cos(t));}
PT rotater(PT a, double t) {return PT(a.x*cos(t)+a.y*sin(t),-a.x*sin(t)+a.y*cos(t));}
double SQ(double x){return x*x;}
double rad_to_deg(double r){return r*180.0/PI;}
double deg_to_rad(double r){return r*PI/180.0;}
double get_angle(PT a,PT b){return acos(max(-1.0,min(1.0,dot(a,b)/a.norm()/b.norm())));}

PT midPT(PT a,PT b){return PT((a.x+b.x)/2.0,(a.y+b.y)/2.0);}

int pt_in_convex_n(vector<PT>&p,PT &x)
{
    int n=p.size()-1;
    int ans=1;
    for(int i=0;i<n;i++)
    {
        int s=turn_l_or_r(Line(p[i],p[i+1]),x);
        ans=min(ans,s);
    }
    return ans;//1 为在内,0在边界,-1在外
}
double pt_dis_line(Line l,PT x)
{
    if(l.s==l.t)return Edis(l.s,x);
    return abs(det(l.t-l.s,x-l.s))/(l.t-l.s).norm();
}
double pt_dis_segment(PT &a,PT &b,PT &x)
{
    double ans=min(Edis(a,x),Edis(b,x));
    double v1=dot(b-a,x-a),v2=dot(b-a,b-a);
    if(sgn(v2-v1)>=0&&sgn(v1)>=0)ans=min(ans,abs(det(b-a,x-a))/(b-a).norm());
    return ans;
}
double pt_dis_convex(vector<PT>&p,PT &x)
{
    int n=p.size()-1;
    double ans=pt_dis_segment(p[0],p[1],x);
    for(int i=1;i<n;i++)ans=min(ans,pt_dis_segment(p[i],p[i+1],x));
    return ans;
}



const int N=2e5+3;
int n;
vector<PT>p;


vector<PT>convex_hull(vector<PT> a)
{
    if(a.size()<=2)return a;
    sort(a.begin(),a.end(),[&](PT u,PT v){return u.x==v.x?u.y<v.y:u.x<v.x;});
    PT stand=p[0];
    sort(a.begin(),a.end(),[&](PT u,PT v){
        int s=sgn(det(u-stand,v-stand));//1 为v在u左侧
        return s!=0?s>0:Edis(u,stand)<Edis(v,stand);
    });
    vector<PT>ret;ret.clear();
    for(auto i:a)
    {
        for(;ret.size()>1&&turn_l_or_r(Line(ret[ret.size()-2],ret[ret.size()-1]),i)<=0;)ret.pop_back();
        ret.push_back(i);
    }
    return ret; 
}


int t;
int d[N];
int main()
{
    rin>>n;
    // p.reserve(n);
    for(int i=0;i<n;i++)
    {
        int x,y;rin>>x>>y;
        // p[i]=PT(x,y);
        p.push_back(PT(x,y));
    }
    // sort(p.begin(),p.end(),[&](PT a,PT b){return a.x==b.x?a.y<b.y:a.x<b.x;});
    // for(int i=0,j;i<n;i=j+1)
    // {
    //     for(j=i;j+1<n&&p[j+1]==p[j];j++);
    //     if(j!=i){puts("No");return 0;}
    //     // pp.push_back(p[i]);
    // }
    vector<PT> convex=convex_hull(p);
    // for(auto i:convex)printf("(%.2lf,%.2lf) ",i.x,i.y);
    if(convex.size()!=n)puts("No");
    else 
    {
        int st;
        for(int i=0;i<n;i++)if(p[i]==convex[0]){st=i;break;}
        for(int i=0;i<n;i++,st++)
        {
            if(st==n)st-=n;
            if(p[st]!=convex[i]){puts("No");return 0;}
        }
        puts("Yes");
    }

    return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

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

input:

3
0 0
1 0
0 1

output:

Yes

result:

ok answer is YES

Test #2:

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

input:

4
0 0
0 1
1 1
1 0

output:

No

result:

wrong answer expected YES, found NO