QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#584237#7906. Almost ConvexgggggggRE 1ms6444kbC++142.5kb2024-09-23 10:41:392024-09-23 10:41:41

Judging History

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

  • [2024-09-23 10:41:41]
  • 评测
  • 测评结果:RE
  • 用时:1ms
  • 内存:6444kb
  • [2024-09-23 10:41:39]
  • 提交

answer

#include<bits/stdc++.h>
#define rep(i,a,b) for(int i=(a);i<=(b);i++)
#define per(i,a,b) for(int i=(a);i>=(b);i--)
#define sz(x) ((int)x.size())
const double eps=1e-8;
const double PI=acos(-1);
using namespace std;
int sgn(double x){
    if(fabs(x)<eps) return 0;
    if(x<0) return -1;
    return 1;
}
struct Point{
    double x,y;
    Point(){}
    Point(double _x,double _y):x(_x),y(_y){}
    Point operator+(const Point &b)const{
        return Point(x+b.x,y+b.y);
    }
    Point operator-(const Point&b)const{
        return Point(x-b.x,y-b.y);
    }
    double operator*(const Point &b)const{
        return x*b.x+y*b.y;
    }
    double operator^(const Point &b)const{ 
        return x*b.y-y*b.x;
    }//cross product
    bool operator<(const Point &b)const{
        return x<b.x||(x==b.x&&y<b.y);
    }
    bool operator==(const Point &b)const{
        return sgn(x-b.x)==0&&sgn(y-b.y)==0;
    }
    Point rotate(Point b,double ang){//Rotate counterclockwise about point b by angle ang
        Point tmp;
        tmp.x=(x-b.x)*cos(ang)-(y-b.y)*sin(ang)+b.x;
        tmp.y=(x-b.x)*sin(ang)+(y-b.y)*cos(ang)+b.y;
        return tmp;
    }
};
vector<Point> ConvexHull(vector<Point> P){
    if(P.size()<3) return P;
    int l=P.size(),tp=-1;
    vector<Point> st;
    st.resize(l);
    sort(P.begin(),P.end());
    st[++tp]=P[0],st[++tp]=P[1];
    for(int i=2;i<l;i++){
        while(tp>=1&&sgn((st[tp]-st[tp-1])^(P[i]-st[tp]))<=0) tp--;
        st[++tp]=P[i];
    }
    st[++tp]=P[l-2];
    int cur=tp;
    for(int i=l-3;i>=0;i--){
        while(tp>=cur&&sgn((st[tp]-st[tp-1])^(P[i]-st[tp]))<=0) tp--;
        st[++tp]=P[i];
    }
    st.resize(tp);
    return st;
}
const int N=2005;
int n,a[N][N],b[N][N],id[N],vs[N];
int main(){
    scanf("%d",&n);
    vector<Point> p(n);
    rep(i,0,n-1) scanf("%lf%lf",&p[i].x,&p[i].y);
    vector<Point> p1=ConvexHull(p);
    rep(i,0,n-1){
        int l=0;
        rep(j,0,n-1) if(i!=j) a[i][l++]=j;
        sort(a[i],a[i]+n-1,[&](int x,int y){return atan2(p[x].y-p[i].y,p[x].x-p[i].x)<atan2(p[y].y-p[i].y,p[y].x-p[i].x);});
        rep(j,0,n-2) b[i][a[i][j]]=j;
    }
    p1.push_back(p1[0]);
    rep(i,0,sz(p1)-1) rep(j,0,n-1) if(p[j]==p1[i]) id[i]=j;
    rep(i,0,sz(p1)-1) vs[id[i]]=1;
    int as=1;
    rep(i,0,sz(p1)-2) rep(j,0,n-1){
        if((p[j]==p1[i])||(p[j]==p1[i+1])||vs[j]) continue;
        int x=b[j][id[i]],y=b[j][id[i+1]];
        if(abs(x-y)==1||(x==0&&y==n-2)||(x==n-2&&y==0)) as++;
    }
    printf("%d\n",as);
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

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

input:

7
1 4
4 0
2 3
3 1
3 5
0 0
2 4

output:

9

result:

ok 1 number(s): "9"

Test #2:

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

input:

5
4 0
0 0
2 1
3 3
3 1

output:

5

result:

ok 1 number(s): "5"

Test #3:

score: -100
Runtime Error

input:

3
0 0
3 0
0 3

output:


result: