QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#109948 | #5570. Epidemic Escape | 2024zll | TL | 1552ms | 7820kb | C++14 | 4.4kb | 2023-05-31 08:16:23 | 2023-05-31 08:16:27 |
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;
}
}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--;
// 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,bool is_up){
/*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=vec.size()-2,mid;
if(is_up)
while(l<r){
mid=(l+r)>>1;
if(Cross(Q-P[vec[mid]],P[vec[mid+1]]-P[vec[mid]])>0)r=mid;
else l=mid+1;
}
else
while(l<r){
mid=(l+r)>>1;
if(Cross(Q-P[vec[mid]],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<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);
/*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');
}*/
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);
Q=Q/sqrt(Dot(Q,Q));
// printf("Q = (%lf, %lf)\n",Q.x,Q.y);
while(!queue.empty())queue.pop();
for(int j=0;j<k;j++)solve(down[j],false);
for(int j=0;j<k;j++)solve(up[j],true);
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)Dot(Q,Q)/dot/2;
static char tmp[100];
sprintf(tmp,"%.10Lf\n",ans);
if(tmp[0]!='n'&&tmp[1]!='n')printf("%.10Lf\n",ans);
else printf("i_%d_Pu_%Lf_%Lf_Q_%Lf_%Lf_dot_%Lf\n",i,P[u].x,P[u].y,Q.x,Q.y,dot);
}
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 0ms
memory: 6112kb
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: 6724kb
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: 3ms
memory: 6324kb
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: 1ms
memory: 6376kb
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: 0
Accepted
time: 1552ms
memory: 7272kb
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:
2.1549170046 2.1672659357 2.0676430855 2.1118419787 2.1118419787 2.1118419787 2.1249872786 2.1213203436 2.0275875101 2.0928822829 2.1415372144 2.0615528128 2.1549170046 2.0000000000 2.1213203436 2.1672659357 2.0676430855 2.0203050891 2.0676430855 2.1415372144 2.1213203436 2.0000000000 2.1213203436 2...
result:
ok 10000 numbers
Test #6:
score: 0
Accepted
time: 27ms
memory: 6504kb
input:
10000 -90174 318421 -37261 138897 -260388 -302590 -906833 35071 317743 -283220 390311 -85301 880987 325969 -315218 -116767 103089 -8223 -134988 -973121 -444593 229407 -552060 549321 265624 -337609 -264546 322379 28687 110143 467764 303005 -335748 32188 213125 274156 240105 751 -81255 -129323 148563 ...
output:
218.3023759373 481.6627119891 792.1850756018 579.9542618493 807.7094462678 242.5921754846 882.2675147667 530.7807802597 664.1821759610 796.3607397675 662.7071678987 639.0726192787 125.8211827153 745.7291752667 732.4967218100 676.5327801482 808.9964118683 427.9627407901 1298.3736892031 616.3789303001...
result:
ok 10000 numbers
Test #7:
score: 0
Accepted
time: 212ms
memory: 7820kb
input:
100000 -14593321 17388753 13488647 1223793 33907737 -8731155 -14502324 73522129 -13933178 -13752140 9462275 13349398 14636622 31405249 5160247 -69775840 -49415260 -40092130 -9926862 -25806124 14982829 -8025116 -5492901 4568113 48872077 86636033 19374632 32538501 -16657133 -11624530 -15398598 -966935...
output:
1331.4977763324 1193.9602287451 1171.2427261871 1856.2890362990 2681.8829458540 1170.8707408363 1128.3614715722 1855.8783379892 3518.3241479702 1541.7860082154 1515.0151223165 1124.4065660466 2146.7167113138 1179.4306789471 1164.1588782715 1251.5110829082 2737.3506509053 1117.3515869945 2213.1263918...
result:
ok 100000 numbers
Test #8:
score: -100
Time Limit Exceeded
input:
100000 -60674143 79489917 99210432 12541486 -99948887 -3196593 57015830 -82153478 10407645 99456921 -90320128 42921703 93983821 34161956 96773928 -25195355 69603194 71801068 27259746 -96212811 96031961 27890165 76618755 -64261689 -99095784 13417302 -95521354 -29591717 -34815155 -93743823 -93393132 -...
output:
49999995.0818661964 49999995.9004091150 49999995.3149217027 49999995.3054674009 49999994.5577050075 49999996.4862814253 49999994.6940732402 49999995.1368904030 49999995.7255437904 49999995.4937630915 49999997.2567733074 49999994.7944017572 49999994.9287077409 49999995.7829386740 49999994.9440986512 ...