QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#110009#5570. Epidemic Escape2024zllWA 19ms6428kbC++145.5kb2023-05-31 09:47:192023-05-31 09:47: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:47:22]
  • 评测
  • 测评结果:WA
  • 用时:19ms
  • 内存:6428kb
  • [2023-05-31 09:47:19]
  • 提交

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,u=up[0].size()-1;i<100;i++,u--)
			printf("%Lf %Lf %d\n",P[up[0][u]].x,P[up[0][u]].y,up[0][u]);
	/*
	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: 1ms
memory: 6316kb

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

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: 4ms
memory: 6368kb

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

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: 19ms
memory: 6428kb

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 0
-0.250000 0.000000 1
-0.250000 0.000000 2
-0.250000 0.000000 3
-0.250000 0.000000 4
-0.250000 0.000000 5
-0.250000 0.000000 6
-0.250000 0.000000 7
-0.250000 0.000000 8
-0.250000 0.000000 9
-0.250000 0.000000 10
-0.250000 0.000000 11
-0.250000 0.000000 12
-0.250000 0.000000 13
-0...

result:

wrong answer 1st numbers differ - expected: '2.1549170', found: '-0.2500000', error = '1.1160137'