QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#584270#7906. Almost ConvexgggggggTL 1ms6480kbC++142.5kb2024-09-23 11:05:142024-09-23 11:05:14

Judging History

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

  • [2024-09-23 11:05:14]
  • 评测
  • 测评结果:TL
  • 用时:1ms
  • 内存:6480kb
  • [2024-09-23 11:05:14]
  • 提交

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(2*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;
    p.resize(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: 6304kb

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

input:

5
4 0
0 0
2 1
3 3
3 1

output:

5

result:

ok 1 number(s): "5"

Test #3:

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

input:

3
0 0
3 0
0 3

output:

1

result:

ok 1 number(s): "1"

Test #4:

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

input:

6
0 0
3 0
3 2
0 2
1 1
2 1

output:

7

result:

ok 1 number(s): "7"

Test #5:

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

input:

4
0 0
0 3
3 0
3 3

output:

1

result:

ok 1 number(s): "1"

Test #6:

score: -100
Time Limit Exceeded

input:

2000
86166 617851
383354 -277127
844986 386868
-577988 453392
-341125 -386775
-543914 -210860
-429613 606701
-343534 893727
841399 339305
446761 -327040
-218558 -907983
787284 361823
950395 287044
-351577 -843823
-198755 138512
-306560 -483261
-487474 -857400
885637 -240518
-297576 603522
-748283 33...

output:


result: