QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#355628 | #5106. Islands from the Sky | InfinityNS# | WA | 1ms | 3948kb | C++14 | 4.0kb | 2024-03-17 00:10:41 | 2024-03-17 00:10:42 |
Judging History
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=1;j<4;j+=2){
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 moze[N][N];
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++)if(moze[i][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){
bool ans=true;
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;
moze[i][j]=true;
}else{
moze[i][j]=false;
}
}
if(!inside){
ans=false;
}
}
return ans;
}
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;
}
詳細信息
Test #1:
score: 100
Accepted
time: 1ms
memory: 3900kb
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: 3948kb
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: 3904kb
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: 1ms
memory: 3920kb
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: 3948kb
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: 3924kb
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: 3892kb
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: 0ms
memory: 3836kb
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