QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#110007 | #5570. Epidemic Escape | 2024zll | WA | 30ms | 6396kb | C++14 | 5.5kb | 2023-05-31 09:45:32 | 2023-05-31 09:45:34 |
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 long 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,Q90;
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--;
// printf("end = %d\n",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);
//printf("top = %d\n",top);
for(int i:stack)used[i]=true/*,printf("%d ",i)*/;
//printf("\n");//for debugging
down.assign(stack.begin(),stack.begin()+k+1);
if(k<top)up.assign(stack.begin()+k+1,stack.begin()+top+1);
}
int k;
struct CMP{
bool operator()(const int x,const int y)const{
return Dot(P[x],Q)>Dot(P[y],Q);
}
}cmp;
std::priority_queue<int,std::vector<int>,CMP>queue;
int vis[maxn],now_id;
void push(const int x){
// printf("push(x = %d)\n",x);
if(vis[x]==now_id||Dot(P[x],Q)<=eps)return;
vis[x]=now_id;
queue.push(x);
if((int)queue.size()>k)/*printf("pop: %d\n",queue.top()),*/queue.pop();
}
void solve(std::vector<int>&vec,const bool flag){
/*printf("vec:");
for(int i:vec)printf(" %d",i);
printf("\n");//for debugging*/
// for(int i:vec)push(i);//for debugging
// return;//for debugging
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(Cross(Q90,P[vec[mid+1]]-P[vec[mid]])>0)r=mid;
else l=mid+1;
// if(n==100)printf("Cross(Q90,(%Lf,%Lf))=%Lf,[%d,%d]\n",P[vec[mid+1]].x-P[vec[mid]].x,P[vec[mid+1]].y-P[vec[mid]].y,Cross(Q90,P[vec[mid+1]]-P[vec[mid]]),l,r);
}
else
while(l<r){
mid=(l+r)>>1;
if(Cross(Q90,P[vec[mid+1]]-P[vec[mid]])>0)l=mid+1;
else r=mid;
// if(n==100)printf("Cross(Q90,(%Lf,%Lf))=%Lf,[%d,%d]\n",P[vec[mid+1]].x-P[vec[mid]].x,P[vec[mid+1]].y-P[vec[mid]].y,Cross(Q90,P[vec[mid+1]]-P[vec[mid]]),l,r);
}
if(n==10000)printf("vec[l = %d] = %d\n",l,vec[l]);
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<n;i++)printf("%lf %lf %d\n",P[i].x,P[i].y,i);
for(int i=0;i<maxk;i++)PolygonToConvex(down[i],up[i],stack);
/*if(n==10000){
puts("up:");
for(int i=0;i<maxk;i++){
for(int j:up[i])printf("%d ",j);
putchar('\n');
}
puts("down:");
for(int i=0;i<maxk;i++){
for(int j:down[i])printf("%d ",j);
putchar('\n');
}
}*/
/*if(n==10000){
for(int i=0;i<maxk;i++)printf("%llu\n",up[i].size());
for(int i=0;i<maxk;i++)printf("%llu\n",down[i].size());
}*/
if(n==10000)
for(int i=0;i<100;i++)
printf("%Lf %Lf %d\n",P[up[0][i]].x,P[up[0][i]].y,up[0][i]);
/*
up:
98 95 59 31 11 2 1 0
96 92 74 42 18 3
91 84 68 49 32 12 6 5 4
87 82 70 60 41 37 30 15 10 8 7
88 73 52 27 26 19 16 14 13
down:
0 35 39 66 99
3 9 28 51 63 97
4 24 40 64 90 94
7 21 29 47 58 86 93
13 23 36 46 62 79 85 89
vec[l = 3] = 66
vec[l = 4] = 11
*/
// if(n==100)
// for(int i:up[0])
// printf("%Lf %Lf\n",P[i].x,P[i].y);
read(q);
memset(vis,-1,sizeof(int)*n);
for(int i=0,x,y;i<q;i++){
now_id=i;
// printf("- - - i = %d - - -\n",i);
read(x),read(y),read(k);
if(x==0&&y==0){
puts("-1");
continue;
}
Q=Vector(x,y);
Q90=Q.rotate_90();
Q=Q/sqrtl(Dot(Q,Q));//sqrtl !!!
// printf("Q = (%lf, %lf)\n",Q.x,Q.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");
continue;
}
const int u=queue.top();
// printf("u = %d\n",u);
const real dot=Dot(P[u],Q);
// printf("dot = %lf\n",dot);
const real ans=(real)0.5/dot;
printf("%.10Lf\n",ans);
if(n==10000)printf("i_%d_k_%d_P%d_%Lf_%Lf_Q_%Lf_%Lf_dot_%Lf\n",i,k,u,P[u].x,P[u].y,Q.x,Q.y,dot);
// i_0_k_1_P98_0.017732_0.009897_Q_0.566529_0.824042_dot_0.018201
}
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 2ms
memory: 6320kb
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: 4ms
memory: 6224kb
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: 6072kb
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: 4ms
memory: 6076kb
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
Wrong Answer
time: 30ms
memory: 6396kb
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:
0.250000 0.000000 9998 0.250000 0.000000 9997 0.250000 0.000000 9996 0.250000 0.000000 9995 0.250000 0.000000 9994 0.250000 0.000000 9993 0.250000 0.000000 9992 0.250000 0.000000 9991 0.250000 0.000000 9990 0.250000 0.000000 9989 0.250000 0.000000 9988 0.250000 0.000000 9987 0.250000 0.000000 9986 0...
result:
wrong answer 1st numbers differ - expected: '2.1549170', found: '0.2500000', error = '0.8839863'