QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#355618#5106. Islands from the SkyInfinityNS#WA 1ms4268kbC++142.6kb2024-03-16 23:19:082024-03-16 23:19:08

Judging History

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

  • [2024-03-16 23:19:08]
  • 评测
  • 测评结果:WA
  • 用时:1ms
  • 内存:4268kb
  • [2024-03-16 23:19:08]
  • 提交

answer

#include <bits/stdc++.h>
using namespace std;
#define ldb 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);

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<0)lo=true;
        if(cr>0)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;
}
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;
    }
    ldb top=90,bot=0;
    bool ok=false;
    for(int it=0;it<30;it++){
        ldb mid=(top+bot)/2;
        //printf("Check %.lf\n",mid);
        if(Check(mid/180*PI,n,m)){
            top=mid;
            ok=true;
        }else bot=mid;
    }
    if(ok){
        printf("%.12lf\n",(top+bot)/2);
    }else{
        printf("impossible\n");
    }
    return 0;
}

详细

Test #1:

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

input:

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

output:

45.000000041910

result:

ok 

Test #2:

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

input:

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

output:

26.565051167272

result:

ok 

Test #3:

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

input:

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

output:

46.686143330298

result:

ok 

Test #4:

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

input:

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

output:

59.491041102447

result:

ok 

Test #5:

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

input:

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

output:

31.219698437490

result:

ok 

Test #6:

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

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.528807730414

result:

ok 

Test #7:

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

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:

45.000000041910

result:

ok 

Test #8:

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

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:

45.000000041910

result:

wrong answer