QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#355621#5106. Islands from the SkyInfinityNS#WA 1ms3952kbC++143.8kb2024-03-16 23:30:552024-03-16 23:30:56

Judging History

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

  • [2024-03-16 23:30:56]
  • 评测
  • 测评结果:WA
  • 用时:1ms
  • 内存:3952kb
  • [2024-03-16 23:30:55]
  • 提交

answer

#include <bits/stdc++.h>
using namespace std;
#define ldb long double
#define pb push_back

struct pt{
    ldb x,y;

    pt():x(0),y(0){}
    pt(ldb a,ldb b):x(a),y(b){}
};

pt operator - (pt a,pt b){return pt(a.x-b.x,a.y-b.y);}
pt operator + (pt a,pt b){return pt(a.x+b.x,a.y+b.y);}
pt operator * (pt a,ldb b){return pt(a.x*b,a.y*b);}
pt operator / (pt a,ldb b){return pt(a.x/b,a.y/b);}

ldb dot(pt a,pt b){return a.x*b.x+a.y*b.y;}
ldb abs(pt a){return sqrt(dot(a,a));}
ldb cross(pt a,pt b){return a.x*b.y-a.y*b.x;}

pt norm(pt a){return a/abs(a);}
pt perp(pt a){return pt(-a.y,a.x);}

const int N=105;
vector<pt> poly[N];

pt from[N],to[N];
int fromZ[N],toZ[N];

pt trapez[N][4];

const ldb PI=acos(-1);
const ldb eps=1e-8;

bool ins(int i,pt p){
    bool hi=false;
    bool lo=false;
    for(int j=0;j<4;j++){
        ldb cr=cross(trapez[i][j]-p,trapez[i][(j+1)%4]-p);
        if(cr<-eps)lo=true;
        if(cr>eps)hi=true;
    }
    return !lo || !hi;
}

bool Check(ldb ang,int n,int m){
    for(int i=1;i<=m;i++){
        pt dir=to[i]-from[i];
        pt v=norm(perp(dir));
        ldb len1=tan(ang)*fromZ[i];
        trapez[i][0]=from[i]+v*len1;
        trapez[i][1]=from[i]-v*len1;
        ldb len2=tan(ang)*toZ[i];
        trapez[i][2]=to[i]-v*len2;
        trapez[i][3]=to[i]+v*len2;
    }
    for(int i=1;i<=n;i++){
        bool inside=false;
        for(int j=1;j<=m;j++){
            bool ok=true;
            for(pt p:poly[i]){
                if(!ins(i,p)){
                    ok=false;
                    break;
                }
            }
            if(ok){
                inside=true;
                break;
            }
        }
        if(!inside)return false;
    }
    return true;
}


#define ll long long
struct pt2{
    ll x,y;

    pt2():x(0),y(0){}
    pt2(ll a,ll b):x(a),y(b){}
};

pt2 operator - (pt2 a,pt2 b){return pt2(a.x-b.x,a.y-b.y);}
pt2 operator + (pt2 a,pt2 b){return pt2(a.x+b.x,a.y+b.y);}

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

pt2 perp(pt2 a){return pt2(-a.y,a.x);}

bool Possible(int n,int m){
    for(int i=1;i<=n;i++){
        bool inside=false;
        for(int j=1;j<=m;j++){
            pt2 A=pt2(round(from[j].x),round(from[j].y));
            pt2 B=pt2(round(to[j].x),round(to[j].y));
            pt2 dir=perp(B-A);

            ll ca=cross(dir,A);
            ll cb=cross(dir,B);
            if(ca>cb)swap(ca,cb);

            bool ok=true;
            for(pt p_:poly[i]){
                pt2 p=pt2(round(p_.x),round(p_.y));
                ll cr=cross(dir,p);
                if(ca<=cr && cr<=cb){
                    continue;
                }else{
                    ok=false;
                    break;
                }
            }
            if(ok){
                inside=true;
                break;
            }
        }
        if(!inside)return false;
    }
    return true;
}
int main(){
    int n,m;
    scanf("%i %i",&n,&m);
    for(int i=1;i<=n;i++){
        int sz;
        scanf("%i",&sz);
        poly[i].resize(sz);
        for(int j=0;j<sz;j++){
            int x,y;
            scanf("%i %i",&x,&y);
            poly[i][j].x=x;
            poly[i][j].y=y;
        }
    }
    for(int i=1;i<=m;i++){
        int x1,y1,x2,y2;
        scanf("%i %i %i %i %i %i",&x1,&y1,&fromZ[i],&x2,&y2,&toZ[i]);
        from[i].x=x1;
        from[i].y=y1;
        to[i].x=x2;
        to[i].y=y2;
    }

    if(Possible(n,m)){
        ldb top=90,bot=0;
        for(int it=0;it<60;it++){
            ldb mid=(top+bot)/2;
            //printf("Check %.lf\n",mid);
            if(Check(mid/180*PI,n,m)){
                top=mid;
            }else bot=mid;
        }
        printf("%.12Lf\n",(top+bot)/2);
    }else{
        printf("impossible\n");
    }
    return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

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

input:

1 1
3
-5 0
5 0
0 5
-10 10 10 10 10 10

output:

44.999999998568

result:

ok 

Test #2:

score: 0
Accepted
time: 0ms
memory: 3928kb

input:

1 1
3
-5 0
5 0
0 5
-10 0 10 10 0 10

output:

26.565051174786

result:

ok 

Test #3:

score: 0
Accepted
time: 0ms
memory: 3936kb

input:

1 1
3
-5 0
5 0
0 5
0 10 10 10 0 10

output:

46.686143339810

result:

ok 

Test #4:

score: 0
Accepted
time: 0ms
memory: 3872kb

input:

1 1
3
-5 0
5 0
0 5
0 10 5 10 0 10

output:

59.491041132127

result:

ok 

Test #5:

score: 0
Accepted
time: 0ms
memory: 3952kb

input:

1 1
3
-5 0
5 0
0 5
0 10 20 -10 0 10

output:

31.219698445675

result:

ok 

Test #6:

score: 0
Accepted
time: 0ms
memory: 3900kb

input:

1 3
3
-5 0
5 0
0 5
-10 0 25 10 0 20
-5 10 10 10 -5 20
-4 1 100 5 10 100

output:

12.528807707938

result:

ok 

Test #7:

score: 0
Accepted
time: 0ms
memory: 3912kb

input:

1 2
4
0 0
20 0
20 40
0 40
-10 30 30 30 30 30
-10 10 30 30 10 30

output:

44.999999999761

result:

ok 

Test #8:

score: -100
Wrong Answer
time: 1ms
memory: 3916kb

input:

1 4
4
0 0
20 0
20 40
0 40
-10 30 30 30 30 30
-10 20 30 30 20 30
-10 10 30 30 10 30
10 -10 30 10 50 30

output:

44.999999999761

result:

wrong answer