QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#88633#5319. Universal Question Answering System2745518585TL 0ms0kbC++146.1kb2023-03-16 20:21:092023-03-16 20:21:11

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:21:11]
  • 评测
  • 测评结果:TL
  • 用时:0ms
  • 内存:0kb
  • [2023-03-16 20:21:09]
  • 提交

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;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 0
Time Limit Exceeded

input:

500
are can X?
everything which can can are Bfheze.
everything can vwya.
everything which can B can B.
everything which can are can Lnx.
can are Tozngr.
everything which can Lnx can B.
can X Qrmoikaxqs?
everything which can Qrmoikaxqs can Qrmoikaxqs.
Bfheze can Lnx.
are which uhsrxrm?
are uhsrxrm ed...

output:


result: