QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#355618 | #5106. Islands from the Sky | InfinityNS# | WA | 1ms | 4268kb | C++14 | 2.6kb | 2024-03-16 23:19:08 | 2024-03-16 23:19:08 |
Judging History
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;
}
Details
Tip: Click on the bar to expand more detailed information
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