QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#88633 | #5319. Universal Question Answering System | 2745518585 | TL | 0ms | 0kb | C++14 | 6.1kb | 2023-03-16 20:21:09 | 2023-03-16 20:21:11 |
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;
}
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...