QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#557009#9253. Prism Palaceucup-team1134AC ✓35ms6444kbC++238.9kb2024-09-10 23:44:532024-09-10 23:44:53

Judging History

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

  • [2024-09-10 23:44:53]
  • 评测
  • 测评结果:AC
  • 用时:35ms
  • 内存:6444kb
  • [2024-09-10 23:44:53]
  • 提交

answer

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
template<class T>bool chmax(T &a, const T &b) { if (a<b) { a=b; return true; } return false; }
template<class T>bool chmin(T &a, const T &b) { if (b<a) { a=b; return true; } return false; }
#define vi vector<int>
#define vl vector<ll>
#define vii vector<pair<int,int>>
#define vll vector<pair<ll,ll>>
#define vvi vector<vector<int>>
#define vvl vector<vector<ll>>
#define vvii vector<vector<pair<int,int>>>
#define vvll vector<vector<pair<ll,ll>>>
#define vst vector<string>
#define pb push_back
#define all(x) (x).begin(),(x).end()
#define mkunique(x) sort(all(x));(x).erase(unique(all(x)),(x).end())
#define fi first
#define se second
#define mp make_pair
#define si(x) int(x.size())
const int mod=998244353,MAX=300005,INF=15<<26;

//幾何ライブラリ(整数)

class Point{
public:
    ll x,y;
    
    Point(ll x=0,ll y=0):x(x),y(y){}
    
    Point operator + (Point p){return Point(x+p.x,y+p.y);}
    Point operator - (Point p){return Point(x-p.x,y-p.y);}
    Point operator * (ll a){return Point(a*x,a*y);}
    
    double norm(){return x*x+y*y;}
    
    bool operator < (const Point &p)const{
        return x<p.x||(x==p.x&&y<p.y);
    }
    
    bool operator == (const Point &p)const{
        return x==p.x&&y==p.y;
    }
};

typedef Point Vector;

ll norm(Vector a){
    return a.x*a.x+a.y*a.y;
}

ll dot(Vector a,Vector b){
    return a.x*b.x+a.y*b.y;
}

ll cross(Vector a,Vector b){
    return a.x*b.y-a.y*b.x;
}

struct Segment{
    Point p1,p2;
};

bool isOrthogonal(Vector a,Vector b){
    return dot(a,b)==0;
}

bool isOrthogonal(Point a1,Point a2,Point b1,Point b2){
    return isOrthogonal(a1-a2,b1-b2);
}

bool isOrthogonal(Segment s1,Segment s2){
    return dot(s1.p2-s1.p1,s2.p2-s2.p1)==0;
}

bool isParallel(Vector a,Vector b){
    return cross(a,b)==0;
}

bool isParallel(Point a1,Point a2,Point b1,Point b2){
    return isParallel(a1-a2,b1-b2);
}

bool isParallel(Segment s1,Segment s2){
    return cross(s1.p2-s1.p1,s2.p2-s2.p1)==0;
}

//p0,p1,p2の順に見たときどうなるか?

static const int counter_clockwise=1;
static const int clockwise=-1;
static const int online_back=2;
static const int online_front=-2;
static const int on_segment=0;

int ccw(Point p0,Point p1,Point p2){
    Vector a=p1-p0;
    Vector b=p2-p0;
    
    if(cross(a,b)>0) return counter_clockwise;
    if(cross(a,b)<0) return clockwise;
    if(dot(a,b)<0) return online_back;
    if(a.norm()<b.norm()) return online_front;
    
    return on_segment;
}

bool intersect(Point p1,Point p2,Point p3,Point p4){
    return(ccw(p1,p2,p3)*ccw(p1,p2,p4)<=0&&ccw(p3,p4,p1)*ccw(p3,p4,p2)<=0);
}

bool intersect(Segment s1,Segment s2){
    return intersect(s1.p1,s1.p2,s2.p1,s2.p2);
}

bool overlap(Segment s1,Segment s2){
    int a=ccw(s1.p1,s1.p2,s2.p1),b=ccw(s1.p1,s1.p2,s2.p2);
    if(a&1||b&1) return 0;
    if(a==2){
        if(b==-2||(b==0&&!(s2.p2==s1.p1))) return 1;
        else return 0;
    }
    if(a==-2){
        if(b==2||(b==0&&!(s2.p2==s1.p2))) return 1;
        else return 0;
    }
    if(a==0){
        if(s1.p1==s2.p1){
            if(b!=2) return 1;
            else return 0;
        }
        else if(s1.p2==s2.p1){
            if(b!=-2) return 1;
            else return 0;
        }
        else return 1;
    }
    return 0;
}
//s1とs2の共通の線分(長さ0より大きい)があるかどうか

typedef Segment Line;

//ネットの適当を書いたのであってるか全く知りません→あってそう

class Circle{
public:
    Point c;
    ll r;
    Circle(Point c=Point(),ll r=0.0):c(c),r(r){}
};

typedef vector<Point> Polygon;

/*
 IN 2
 ON 1
 OUT 0
 */

int contains(Polygon g,Point p){
    int n=int(g.size());
    bool x=false;
    for(int i=0;i<n;i++){
        Point a=g[i]-p,b=g[(i+1)%n]-p;
        if(a.y>b.y) swap(a,b);
        if(a.y<=0&&0<b.y&&cross(a,b)<0) x=!x;
        if(abs(cross(a,b))<=0&&dot(a,b)<=0) return 1;
    }
    return (x?2:0);
}
//ayasii

Polygon andrewScan(Polygon s,bool ok){
    Polygon u,l;
    sort(all(s));
    
    if(int(s.size())<3) return s;
    int n=int(s.size());
    
    u.push_back(s[0]);
    u.push_back(s[1]);
    
    l.push_back(s[n-1]);
    l.push_back(s[n-2]);
    
    if(ok){
        for(int i=2;i<n;i++){
            for(int j=int(u.size());j>=2&&ccw(u[j-2],u[j-1],s[i])==counter_clockwise;j--){
                u.pop_back();
            }
            u.push_back(s[i]);
        }
        
        for(int i=int(s.size())-3;i>=0;i--){
            for(int j=int(l.size());j>=2&&ccw(l[j-2],l[j-1],s[i])==counter_clockwise;j--){
                l.pop_back();
            }
            l.push_back(s[i]);
        }
    }
    
    if(!ok){
        for(int i=2;i<n;i++){
            for(int j=int(u.size());j>=2&&ccw(u[j-2],u[j-1],s[i])!=clockwise;j--){
                u.pop_back();
            }
            u.push_back(s[i]);
        }
        
        for(int i=int(s.size())-3;i>=0;i--){
            for(int j=int(l.size());j>=2&&ccw(l[j-2],l[j-1],s[i])!=clockwise;j--){
                l.pop_back();
            }
            l.push_back(s[i]);
        }
    }
    
    reverse(all(l));
    
    for(int i=int(u.size())-2;i>=1;i--) l.push_back(u[i]);
    
    return l;
}//ok==1なら辺の上も含める

ll area(Polygon P){
    ll sum=0;
    for(int i=0;i<si(P);i++){
        sum+=cross(P[i],P[(i+1)%si(P)]);
    }
    return abs(sum);
}

// 倍

ll gcd(ll a,ll b){
    if(b==0) return a;
    return gcd(b,a%b);
}

pair<Point,Vector> perpendicular_bisector(Point a,Point b){
    Point c;
    c.x=(a.x+b.x)/2;
    c.y=(a.y+b.y)/2;
    Vector v=b-c;
    swap(v.x,v.y);
    v.x*=-1;
    
    Point p=c;
    if(v.x==0){
        v.y=1;
        p.y=0;
    }
    else if(v.y==0){
        v.x=1;
        p.x=0;
    }
    else{
        if(v.x<0){
            v.x*=-1;
            v.y*=-1;
        }
        ll g=gcd(abs(ll(v.x)),abs(ll(v.y)));
        v.x/=g;
        v.y/=g;
        if(p.x>=0){
            ll d=p.x/v.x;
            p=p-v*d;
        }else{
            ll d=abs(p.x)/v.x;
            p=p+v*d;
            
            if(p.x<0){
                p=p+v;
            }
        }
    }
    
    return mp(p,v);
}
//2倍するなりして整数にしておくこと


int main(){
    
    std::ifstream in("text.txt");
    std::cin.rdbuf(in.rdbuf());
    cin.tie(0);
    ios::sync_with_stdio(false);
    
    ll N;cin>>N;
    if(N==3){
        cout<<1<<endl;
        return 0;
    }
    
    vector<Point> P(N);
    for(int i=0;i<N;i++) cin>>P[i].x>>P[i].y;
    
    double res=0;
    
    for(int i=0;i<N;i++){
        Point a=P[i],b=P[(i+1)%N],c=P[(i+2)%N],d=P[(i+3)%N];
        double sum=0;
        sum+=acos((double)(dot(a-b,c-b))/sqrt(norm(a-b))/sqrt(norm(c-b)));
        sum+=acos((double)(dot(b-c,d-c))/sqrt(norm(b-c))/sqrt(norm(d-c)));
        if(sum<acos(-1)) res+=acos(-1)-sum;
    }
    
    res/=acos(-1);
    
    cout<<fixed<<setprecision(25)<<res<<endl;
    
    return 0;
    
    /*
     
     mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
     
     while(1){
     ll N=rng()%100+1;
     vector<Point> P(N);
     for(int i=0;i<N;i++){
     ll x=abs(ll(rng()%200))-100,y=abs(ll(rng()%200))-100;
     P[i]={x,y};
     }
     P=andrewScan(P,0);
     N=si(P);
     /*
     P.resize(N);
     P[0]={0,0};
     P[1]={1,1};
     P[2]={1,2};
     P[3]={0,3};
     N=4;
     //if(N>=5) continue;
     if(N!=5) continue;
     ll s=0,t=0;
     
     vector<double> VV;
     for(ll q=0;q<10000;q++){
     ll x=abs((ll)(rng()%200000000))-100000000,y=abs((ll)(rng()%200000000))-100000000;
     if(x*x+y*y<=100000000LL*100000000){
     t++;
     vl S(N);
     for(int i=0;i<N;i++){
     Vector v=P[(i+1)%N]-P[i],vv={x,y};
     S[i]=abs(cross(v,vv));
     }
     sort(all(S));
     bool f=false;
     
     for(int bit=0;bit<(1<<N);bit++){
     ll sum=0;
     for(int i=0;i<N;i++){
     if(bit&(1<<i)) sum+=S[i];
     }
     if(sum%2==0&&binary_search(all(S),sum/2)) f=true;
     }
     
     if(f){
     s++;
     VV.pb(atan2(y,x));
     }
     }
     }
     //if(s==t||s==0) continue;
     double ss=0;
     for(int i=0;i<N;i++){
     Point a=P[i],b=P[(i+1)%N],c=P[(i+2)%N],d=P[(i+3)%N];
     Vector e=d-c,f=a-b;
     Vector O={0,0};
     int cc=ccw(e,O,f);
     if(cc==counter_clockwise){
     ss+=acos((double)(dot(f,e))/sqrt(norm(e))/sqrt(norm(f)));
     }
     }
     ss/=M_PI;
     cout<<N<<" "<<s<<" "<<t<<" "<<(double)(s)/t<<" "<<ss<<endl;
     continue;
     sort(all(VV));
     for(auto [a,b]:P) cout<<"("<<a<<","<<b<<")"<<endl;
     int i=0;
     while(i<si(VV)){
     int j=i;
     while(j+1<si(VV)&&VV[j+1]-VV[j]<=0.05) j++;
     cout<<VV[i]<<" "<<VV[j]<<endl;
     i=j+1;
     }
     //return 0;
     }
     
     */
}

这程序好像有点Bug,我给组数据试试?

Details

Tip: Click on the bar to expand more detailed information

Test #1:

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

input:

3
0 0
1 0
0 1

output:

1

result:

ok found '1.0000000', expected '1.0000000', error '0.0000000'

Test #2:

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

input:

4
0 0
0 1
1 1
1 0

output:

0.0000000000000000000000000

result:

ok found '0.0000000', expected '0.0000000', error '-0.0000000'

Test #3:

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

input:

4
0 0
0 3
1 2
1 1

output:

0.4999999999999999444888488

result:

ok found '0.5000000', expected '0.5000000', error '0.0000000'

Test #4:

score: 0
Accepted
time: 35ms
memory: 6376kb

input:

199996
719157942 80035870
719158808 80033199
719160795 80027070
719162868 80020675
719165635 80012139
719166422 80009711
719166927 80008153
719168388 80003645
719168539 80003179
719168806 80002355
719168864 80002176
719169119 80001389
719171067 79995376
719173806 79986921
719175195 79982633
71917686...

output:

0.0000777168034902920950007

result:

ok found '0.0000777', expected '0.0000777', error '0.0000000'

Test #5:

score: 0
Accepted
time: 32ms
memory: 6204kb

input:

199999
521578765 315995242
521578784 315995230
521585008 315991299
521590377 315987908
521597318 315983524
521606119 315977965
521610976 315974897
521614329 315972779
521622922 315967351
521631939 315961655
521636172 315958981
521638241 315957674
521643115 315954595
521650976 315949629
521656567 315...

output:

0.0000965321793526363022874

result:

ok found '0.0000965', expected '0.0000965', error '0.0000000'

Test #6:

score: 0
Accepted
time: 35ms
memory: 6444kb

input:

200000
88808852 208512084
88810113 208513562
88812008 208515783
88812543 208516410
88816806 208521406
88824507 208530431
88825624 208531740
88831723 208538887
88834262 208541862
88838287 208546578
88845440 208554959
88848801 208558897
88855564 208566821
88856869 208568350
88862876 208575388
88868324...

output:

0.0000743737012955406290391

result:

ok found '0.0000744', expected '0.0000744', error '0.0000000'

Test #7:

score: 0
Accepted
time: 35ms
memory: 6280kb

input:

199998
2857588 37580055
2857908 37582176
2857951 37582461
2858026 37582958
2859295 37591366
2859678 37593903
2860879 37601857
2862301 37611272
2862330 37611464
2863054 37616255
2864429 37625353
2865434 37632002
2865585 37633001
2867092 37642971
2867321 37644486
2867870 37648118
2868343 37651247
2868...

output:

0.0000675396834444813251065

result:

ok found '0.0000675', expected '0.0000675', error '0.0000000'

Test #8:

score: 0
Accepted
time: 35ms
memory: 6280kb

input:

199999
487716180 333296644
487720319 333294576
487721706 333293883
487731571 333288954
487734599 333287441
487742738 333283374
487744419 333282534
487746174 333281657
487748301 333280594
487750462 333279514
487754846 333277323
487759670 333274912
487762097 333273699
487764676 333272410
487772963 333...

output:

0.0000706967017867891108895

result:

ok found '0.0000707', expected '0.0000707', error '0.0000000'

Extra Test:

score: 0
Extra Test Passed