QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#110026 | #5570. Epidemic Escape | 2024zll | WA | 0ms | 5352kb | C++14 | 3.5kb | 2023-05-31 10:24:50 | 2023-05-31 10:24:52 |
Judging History
answer
#include<algorithm>
#include<cmath>
#include<cstdio>
#include<cstring>
#include<queue>
#include<vector>
namespace IO{
const int ARR_SIZE=1<<20;
#define gc() ((IO::si!=IO::ti||(IO::ti=(IO::si=IO::input)+fread(IO::input,1,IO::ARR_SIZE,stdin))),IO::si!=IO::ti?*(IO::si++):EOF)
char input[ARR_SIZE],*si=input,*ti=input;
template<typename T>
void read(T&num){
bool flag=true;
int ch=gc();
num=0;
while(ch<48||ch>57){
if(ch=='-')flag=false;
ch=gc();
}
while(ch>=48&&ch<=57)num=num*10+(ch^48),ch=gc();
flag||(num=-num);
}
}
using IO::read;
typedef double real;
const int maxn=100000,maxk=5;
const real eps=1e-16;
int n,q;
struct Vector{
real x,y;
Vector(const real x=0,const real y=0):x(x),y(y){}
friend bool operator<(const Vector&A,const Vector&B){
return A.x!=B.x?A.x<B.x:A.y<B.y;
}
friend Vector operator-(const Vector&A,const Vector&B){
return Vector(A.x-B.x,A.y-B.y);
}
friend Vector operator/(const Vector&A,const real&x){
return Vector(A.x/x,A.y/x);
}
friend real Cross(const Vector&A,const Vector&B){
return A.x*B.y-A.y*B.x;
}
friend real Dot(const Vector&A,const Vector&B){
return A.x*B.x+A.y*B.y;
}
Vector rotate_90(){
return Vector(-y,x);
}
}P[maxn],Q;
bool used[maxn];
std::vector<int>down[maxk],up[maxk],stack;
void PolygonToConvex(std::vector<int>&down,std::vector<int>&up,std::vector<int>&stack){
int end=n-1;
while(end>=0&&used[end])end--;
if(end==-1)return;
stack.resize(n*2);
int top=-1;
for(int i=0;i<=end;i++){
if(used[i])continue;
while(top>0&&Cross(P[stack[top]]-P[stack[top-1]],P[i]-P[stack[top]])<=0)top--;
stack[++top]=i;
}
const int k=top;
for(int i=end-1;i>=0;i--){
if(used[i])continue;
while(top>k&&Cross(P[stack[top]]-P[stack[top-1]],P[i]-P[stack[top]])<=0)top--;
stack[++top]=i;
}
stack.resize(top+1);
for(int i:stack)used[i]=true;
down.assign(stack.begin(),stack.begin()+k+1);
if(k<top)up.assign(stack.begin()+k+1,stack.begin()+top+1);
}
int k;
real DotPQ[maxn];
struct CMP{
bool operator()(const int x,const int y)const{
return DotPQ[x]>DotPQ[y];
}
}cmp;
std::priority_queue<int,std::vector<int>,CMP>queue;
int vis[maxn],now_id;
void push(const int x){
if(vis[x]==now_id)return;
vis[x]=now_id;
if((DotPQ[x]=Dot(P[x],Q))<=eps)return;
queue.push(x);
if((int)queue.size()>k)queue.pop();
}
void solve(std::vector<int>&vec,const bool flag){
if((int)vec.size()<=k)
for(int i:vec)
push(i);
else{
for(int i=0;i<k;i++)push(vec[i]);
for(int i=(int)vec.size()-k;i<(int)vec.size();i++)push(vec[i]);
int l=0,r=(int)vec.size()-2,mid;
if(flag)
while(l<r){
mid=(l+r)>>1;
if(Dot(Q,P[vec[mid+1]]-P[vec[mid]])<0)r=mid;
else l=mid+1;
}
else
while(l<r){
mid=(l+r)>>1;
if(Dot(Q,P[vec[mid+1]]-P[vec[mid]])<0)l=mid+1;
else r=mid;
}
for(int i=std::max(0,l-k),lim=std::min((int)vec.size()-1,l+k);i<=lim;i++)push(vec[i]);
}
}
int main(){
read(n);
for(int i=0;i<n;i++)read(P[i].x),read(P[i].y),P[i]=P[i]/Dot(P[i],P[i]);
std::sort(P,P+n);
for(int i=0;i<maxk;i++)PolygonToConvex(down[i],up[i],stack);
read(q);
memset(vis,-1,sizeof(int)*n);
for(int i=0,x,y;i<q;i++){
now_id=i;
read(x),read(y),read(k);
if(x==0&&y==0){
puts("-1");
continue;
}
Q=Vector(x,y);
while(!queue.empty())queue.pop();
for(int j=0;j<k;j++)solve(down[j],y<0);
for(int j=0;j<k;j++)solve(up[j],y>0);
if((int)queue.size()<k)puts("-1");
else printf("%.7lf\n",(real)0.5/Dot(P[queue.top()],Q)/sqrt(Dot(Q,Q)));
}
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 0
Wrong Answer
time: 0ms
memory: 5352kb
input:
5 5 -3 5 4 -6 2 -5 0 4 1 2 -3 -10 1 6 -9 1
output:
0.0798189 0.0275728
result:
wrong answer 1st numbers differ - expected: '8.7002554', found: '0.0798189', error = '0.9908257'