QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#88634 | #5570. Epidemic Escape | 2745518585 | RE | 21ms | 97172kb | C++14 | 6.1kb | 2023-03-16 20:21:34 | 2023-03-16 20:21:39 |
Judging History
answer
#include<cstdio>
#include<algorithm>
#include<cmath>
#include<vector>
using namespace std;
typedef long double ld;
inline char gc()
{
static char buf[100000],*p1=buf,*p2=buf;
return p1==p2&&(p2=(p1=buf)+fread(buf,1,100000,stdin),p1==p2)?EOF:*p1++;
}
template<typename T>
inline void read(T &x)
{
T u=1,t=0;char c=gc();
while(c<'0'||c>'9') {if(c=='-') u=-1; c=gc();}
while(c>='0'&&c<='9') t*=10,t+=c-'0',c=gc();
x=u*t;return;
}
const double eps=1e-12,pi=acos(-1.0);
const int N=4000001;
int dcmp(double x)
{
if(fabs(x)<eps) return 0;
if(x>0) return 1;
return -1;
}
struct point
{
double x,y;
point(){}
point(double x,double y):x(x),y(y){}
friend point operator+(point a,point b)
{
return point(a.x+b.x,a.y+b.y);
}
friend point operator-(point a,point b)
{
return point(a.x-b.x,a.y-b.y);
}
friend point operator*(point a,double b)
{
return point(a.x*b,a.y*b);
}
friend point operator*(double b,point a)
{
return point(a.x*b,a.y*b);
}
friend point operator/(point a,double b)
{
return point(a.x/b,a.y/b);
}
friend double dot(point a,point b)
{
return a.x*b.x+a.y*b.y;
}
friend double cross(point a,point b)
{
return a.x*b.y-a.y*b.x;
}
friend double length(point a)
{
return sqrt(a.x*a.x+a.y*a.y);
}
};
struct line
{
point a,b;
int t;
line(){}
line(point a,point b):a(a),b(b){}
line(point a,point b,int t):a(a),b(b),t(t){}
};
double angle(point a,point b)
{
return acos(dot(a,b)/length(a)/length(b));
}
double disPP(point a,point b)
{
return sqrt((a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y));
}
bool onleftPL(point a,line b)
{
return dcmp(cross(a-b.a,b.b))<0;
}
point intLL(line a,line b)
{
if(dcmp(cross(a.b,b.b))==0) return point(1e30,1e30);
return a.a+(cross(b.b,a.a-b.a)/cross(a.b,b.b))*a.b;
}
point turnV(point a,double b)
{
return point(a.x*cos(b)-a.y*sin(b),a.y*cos(b)+a.x*sin(b));
}
struct halfplane
{
int m,n;
line a[N],b[N];
double s;
static bool cmp(line a,line b)
{
return atan2(a.b.y,a.b.x)<atan2(b.b.y,b.b.x);
}
void solve()
{
sort(b+1,b+m+1,cmp);
int T=1,R=0;
a[++R]=b[1];
for(int i=2;i<=m;++i)
{
while(T<=R-1&&!onleftPL(intLL(a[R-1],a[R]),b[i])) --R;
while(T<=R-1&&!onleftPL(intLL(a[T],a[T+1]),b[i])) ++T;
a[++R]=b[i];
if(T<=R-1&&dcmp(cross(a[R].b,a[R-1].b))==0)
{
if(dcmp(cross(a[R-1].a-a[R].a,a[R].b))>=0&&dcmp(dot(a[R-1].b,a[R].b))<0)
{
n=0;
return;
}
if(dcmp(dot(a[R-1].b,a[R].b))>0)
{
if(dcmp(cross(a[R-1].a-a[R].a,a[R].b))>0) swap(a[R],a[R-1]);
--R;
}
}
}
while(T<=R-1&&!onleftPL(intLL(a[R-1],a[R]),a[T])) --R;
n=R-T+1;
if(n<=2) n=0;
for(int i=1;i<=n;++i)
{
a[i]=a[T+i-1];
}
a[n+1]=a[1];
a[n+2]=a[2];
}
double area()
{
double s=0;
a[n+1]=a[1];
a[n+2]=a[2];
for(int i=1;i<=n;++i)
{
s+=cross(intLL(a[i],a[i+1]),intLL(a[i+1],a[i+2]))/2;
}
return s;
}
}S;
int n,m,t;
double e[N],f[N];
bool h[N];
line a[N],c[N];
struct str
{
point x;
int k,t;
}b[N];
vector<int> d[N];
bool cmp(str a,str b)
{
return atan2(a.x.y,a.x.x)<atan2(b.x.y,b.x.x);
}
void solve()
{
S.m=0;
for(int i=1;i<=n;++i)
{
if(h[i]==false) S.b[++S.m]=a[i];
}
S.b[++S.m]=line(point(1e18,1e18),point(-1,0),0);
S.b[++S.m]=line(point(-1e18,1e18),point(0,-1),0);
S.b[++S.m]=line(point(-1e18,-1e18),point(1,0),0);
S.b[++S.m]=line(point(1e18,-1e18),point(0,1),0);
S.solve();
int n=S.n;
for(int i=1;i<=n;++i)
{
c[i]=c[n+i]=c[n*2+i]=c[n*3+i]=S.a[i];
h[c[i].t]=true;
}
auto dis=[&](int x,int i)
{
if(dcmp(dot(b[i].x,intLL(c[x],line(point(0,0),b[i].x))))<0) return (double)1e30;
return length(intLL(c[x],line(point(0,0),b[i].x)));
};
int x=n+1;
for(int i=1;i<=m;++i)
{
while(dis(x,i)>1e25||dis(x+1,i)<dis(x,i)) ++x;
d[i].push_back(c[x-4].t);
d[i].push_back(c[x-3].t);
d[i].push_back(c[x-2].t);
d[i].push_back(c[x-1].t);
d[i].push_back(c[x].t);
d[i].push_back(c[x+1].t);
d[i].push_back(c[x+2].t);
d[i].push_back(c[x+3].t);
d[i].push_back(c[x+4].t);
}
}
int main()
{
read(n);
for(int i=1;i<=n;++i)
{
point x;
int z;
read(z);
x.x=z;
read(z);
x.y=z;
if(dcmp(x.x)==0&&dcmp(x.y)==0)
{
++t,--n,--i;
continue;
}
a[i]=line(x/2,turnV(x,pi/2),i);
if(dcmp(cross(a[i].b,point(0,0)-a[i].a))<0) a[i].b=point(0,0)-a[i].b;
}
read(m);
for(int i=1;i<=m;++i)
{
int z;
read(z);
b[i].x.x=z;
read(z);
b[i].x.y=z;
read(b[i].k);
b[i].t=i;
}
sort(b+1,b+m+1,cmp);
for(int i=1;i<=5;++i) solve();
for(int i=1;i<=m;++i)
{
int z=0;
sort(d[i].begin(),d[i].end());
for(int j=0;j<d[i].size();++j)
{
if((j>0&&d[i][j]==d[i][j-1])||d[i][j]==0) continue;
point p=intLL(line(point(0,0),b[i].x),a[d[i][j]]);
if(dcmp(dot(b[i].x,p))>0) e[++z]=disPP(point(0,0),p);
else e[++z]=1e30;
}
sort(e+1,e+z+1);
if(t>=b[i].k) f[b[i].t]=0;
else if(e[b[i].k-t]>1e17) f[b[i].t]=-1;
else f[b[i].t]=e[b[i].k-t];
}
for(int i=1;i<=m;++i)
{
if(f[i]<0) printf("-1\n");
else printf("%.10lf\n",f[i]);
}
return 0;
}
详细
Test #1:
score: 100
Accepted
time: 21ms
memory: 97168kb
input:
5 5 -3 5 4 -6 2 -5 0 4 1 2 -3 -10 1 6 -9 1
output:
8.7002554241 3.2260195623
result:
ok 2 numbers
Test #2:
score: 0
Accepted
time: 19ms
memory: 97116kb
input:
8 4 -1 4 -8 0 9 4 -7 -5 -2 5 -5 7 5 -9 2 10 4 -8 1 7 -7 5 -10 8 2 -9 9 2 4 -7 5 -1 -10 2 6 -3 2 2 -9 3 -10 -10 1 5 9 1
output:
3.1677629681 26.1629509039 5.4614883202 6.3639610307 -1 5.2894082216 3.7267799625 4.6097722286 2.9294423792 4.7617289402
result:
ok 10 numbers
Test #3:
score: 0
Accepted
time: 18ms
memory: 97124kb
input:
5 -4 -7 5 0 2 4 -7 -7 4 4 20 0 -5 2 -4 -7 2 -7 7 3 4 -4 3 -7 4 3 4 -4 1 2 4 1 6 -7 2 4 -4 2 4 4 3 5 4 1 -1 9 2 8 9 3 4 -4 2 6 3 3 -10 -3 2 -7 7 1 9 -4 1 -4 -7 3 -2 0 2
output:
7.0000000000 5.1305276580 -1 -1 -1 3.5355339059 2.2360679775 11.9854077945 15.3206469257 3.5355339059 2.4627400913 4.5276925691 3.7629983059 15.3206469257 2.9814239700 5.6217035048 7.0710678119 2.7357938338 -1 8.1250000000
result:
ok 20 numbers
Test #4:
score: 0
Accepted
time: 20ms
memory: 97172kb
input:
100 63 -48 20 -62 -81 -31 -17 -93 2 -74 72 25 -71 37 -71 17 56 67 -47 65 -89 14 62 30 -71 -33 14 -53 -57 -52 30 80 -14 -69 -45 -19 -54 -71 58 -20 -57 12 5 -56 -76 -2 26 61 24 60 10 -97 -63 38 17 81 -43 -38 44 35 -86 37 62 72 77 11 41 29 14 81 77 55 -54 -33 -43 -51 76 14 55 47 43 24 69 -13 16 75 11 9...
output:
26.7586788688 29.5714059979 24.6221445045 27.7717456547 26.6783667129 24.4237024605 28.8933481964 29.7761695578 31.9403629705 27.2149016024 31.7280950457 27.0711605517 25.2991100306 26.8710651521 28.9958394534 28.3563142462 29.9872588920 25.6496237196 25.1496681332 28.3011569706 28.6117519545 26.690...
result:
ok 100 numbers
Test #5:
score: -100
Runtime Error
input:
10000 -3 3 -6 2 -4 1 -2 -5 5 -6 -7 -2 0 7 1 -4 8 0 -4 4 -6 -2 5 0 2 9 -4 -8 0 -8 7 4 -7 2 3 3 4 1 -1 7 -4 -2 6 0 3 -5 -7 2 0 -9 7 0 7 3 -6 0 1 7 6 2 2 -9 1 8 3 -3 2 -9 4 2 4 -5 6 0 -3 6 7 3 0 8 0 -4 7 0 -5 8 5 -5 -5 -1 0 9 -4 -3 -9 -1 7 -2 -7 -2 4 0 -6 6 -3 4 6 7 2 5 -8 -5 0 5 4 0 0 -4 0 -6 -5 3 -5 ...