QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#110007#5570. Epidemic Escape2024zllWA 30ms6396kbC++145.5kb2023-05-31 09:45:322023-05-31 09:45:34

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:45:34]
  • 评测
  • 测评结果:WA
  • 用时:30ms
  • 内存:6396kb
  • [2023-05-31 09:45:32]
  • 提交

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'