QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#390015 | #5106. Islands from the Sky | 0_GB_RAM# | WA | 1898ms | 4484kb | C++23 | 3.0kb | 2024-04-15 00:00:29 | 2024-04-15 00:00:30 |
Judging History
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