QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#390015#5106. Islands from the Sky0_GB_RAM#WA 1898ms4484kbC++233.0kb2024-04-15 00:00:292024-04-15 00:00:30

Judging History

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

  • [2024-04-15 00:00:30]
  • 评测
  • 测评结果:WA
  • 用时:1898ms
  • 内存:4484kb
  • [2024-04-15 00:00:29]
  • 提交

answer

#include <bits/stdc++.h>
using namespace std;

using ll=long long;
//#define int ll
#define rep(i,a,b) for(int i=a;i<(b);++i)
#define all(x) begin(x),end(x)
#define sz(x) (int)((x).size())
using pii=pair<int,int>;
using vi=vector<int>;
#define fi first
#define se second
#define pb push_back

const int N=110;

vector<pii> polys[N];
pair<array<int,3>,array<int,3>> paths[N];
bool ok[N];

bool small(pair<double,double> a,pair<double,double> b,pair<double,double> c)
{
    a.fi-=b.fi;
    a.se-=b.se;
    c.fi-=b.fi;
    c.se-=b.se;
    return a.fi*c.se-a.se*c.fi>=0;
}

signed main() {
	cin.tie(0)->sync_with_stdio(0);
    cin.exceptions(cin.failbit);

    int n,m;
    cin>>n>>m;
    for(int i=1;i<=n;i++)
    {
        int k;
        cin>>k;
        polys[i].resize(k);
        for(auto&[x,y]:polys[i])
            cin>>x>>y;
    }
    for(int i=1;i<=m;i++)
        cin>>paths[i].fi[0]>>paths[i].fi[1]>>paths[i].fi[2]>>paths[i].se[0]>>paths[i].se[1]>>paths[i].se[2];
    double lo=0,hi=M_PI;
//    lo=hi=48.031693036*M_PI/180;
    bool pos=false;
    while(clock()*1.0/CLOCKS_PER_SEC<1.9)
    {
        double mi=(lo+hi)/2;
        for(int i=1;i<=n;i++)
            ok[i]=false;
        for(int i=1;i<=m;i++)
        {
            auto[p1,p2]=paths[i];
            auto[x1,y1,z1]=p1;
            auto[x2,y2,z2]=p2;
            double a=y2-y1;
            double b=x1-x2;
            double s=sqrt((ll)a*a+(ll)b*b);
            a/=s;
            b/=s;

            double d1=z1*tan(mi);
            pair q1(x1+a*d1,y1+b*d1);
            pair q2(x1-a*d1,y1-b*d1);

            double d2=z2*tan(mi);
            pair q3(x2-a*d2,y2-b*d2);
            pair q4(x2+a*d2,y2+b*d2);

//            cout<<q1.fi<<" "<<q1.se<<"\n";
//            cout<<q2.fi<<" "<<q2.se<<"\n";
//            cout<<q3.fi<<" "<<q3.se<<"\n";
//            cout<<q4.fi<<" "<<q4.se<<"\n";
//            cout<<"\n";

            auto check=[&](pii p)
            {
                bool b1=small(q1,p,q2);
                bool b2=small(q2,p,q3);
                bool b3=small(q3,p,q4);
                bool b4=small(q4,p,q1);
//                cout<<b1<<b2<<b3<<b4<<"\n";
                return b1==b2&&b1==b3&&b1==b4;
            };

            for(int j=1;j<=n;j++)
                if(!ok[j])
                {
                    bool cur=true;
                    for(auto p:polys[j])
                        if(!check(p))
                        {
                            cur=false;
                            break;
                        }
                    if(cur)
                        ok[j]=true;
                }
        }

        bool ans=true;
        for(int j=1;j<=n;j++)
            if(!ok[j])
            {
                ans=false;
                break;
            }
        if(ans)
            pos=true;
        (ans?hi:lo)=mi;
    }
    if(!pos) cout<<"impossible"; else
    cout<<fixed<<setprecision(10)<<(lo+hi)/2*180/M_PI;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 916ms
memory: 4484kb

input:

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

output:

45.0000000000

result:

ok 

Test #2:

score: 0
Accepted
time: 958ms
memory: 4476kb

input:

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

output:

26.5650511771

result:

ok 

Test #3:

score: 0
Accepted
time: 1198ms
memory: 4464kb

input:

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

output:

46.6861433417

result:

ok 

Test #4:

score: -100
Wrong Answer
time: 1898ms
memory: 4276kb

input:

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

output:

impossible

result:

wrong answer