QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#109995#5570. Epidemic Escape2024zllWA 27ms6556kbC++145.3kb2023-05-31 09:23:202023-05-31 09:23:22

Judging History

你现在查看的是最新测评结果

  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2023-05-31 09:23:22]
  • 评测
  • 测评结果:WA
  • 用时:27ms
  • 内存:6556kb
  • [2023-05-31 09:23:20]
  • 提交

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');
		}
	}
	/*
	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: 4ms
memory: 6164kb

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: 6068kb

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: 6360kb

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: 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: 27ms
memory: 6556kb

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:

up:
9998 9997 9996 9995 9994 9993 9992 9991 9990 9989 9988 9987 9986 9985 9984 9983 9982 9981 9980 9979 9978 9977 9976 9975 9974 9973 9972 9971 9970 9969 9968 9967 9966 9965 9964 9963 9962 9961 9960 9959 9958 9957 9956 9955 9954 9953 9952 9951 9950 9949 9948 9947 9946 9945 9944 9943 9942 9941 9940 9...

result:

wrong output format Expected double, but "up:" found