QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#88632#5570. Epidemic Escape2745518585RE 5ms27760kbC++146.1kb2023-03-16 20:20:072023-03-16 20:20:08

Judging History

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

  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2023-03-16 20:20:08]
  • 评测
  • 测评结果:RE
  • 用时:5ms
  • 内存:27760kb
  • [2023-03-16 20:20:07]
  • 提交

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=1000001;
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: 5ms
memory: 26772kb

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: 3ms
memory: 27760kb

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: 1ms
memory: 26912kb

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: 0ms
memory: 26896kb

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 ...

output:


result: