Submission #4072

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
4072	2013-08-31T18:47:52 Z	ainta	Jogging (kriii1_J)	C++	1 / 1	104 ms	3656 KB

J

#include<stdio.h>
#include<algorithm>
#include<math.h>
#define INF 1e9
using namespace std;
struct point{
	int x,y;
	bool operator <(const point &p)const{
		return x<p.x;
	}
}w[100001];
int X[100001],n,m,i,st[100001],top;
double Res[100001];
double F(int a,int b){
	double A=w[a].y;
	A=A*(w[b].x-w[a].x);
	A=A/(w[b].y-w[a].y);
	A=w[a].x-A;
	return A;
}
int main()
{
	scanf("%d%d",&n,&m);
	for(i=0;i<n;i++){
		scanf("%d%d",&w[i].x,&w[i].y);
	}
	sort(w,w+n);
	for(i=0;i<m;i++)scanf("%d",&X[i]);
	int pv=m-1;
	for(i=n-1;i>=-1;i--){
		while(i==-1 || X[pv]>=w[i].x){
			while(top>1 && F(st[top],st[top-1])>=X[pv])top--;
			if(top==0)Res[pv]=0;
			else{
				Res[pv]=atan2(w[st[top]].y,w[st[top]].x-X[pv]);
			}
			pv--;
			if(pv<0)break;
		}
		if(pv<0)break;
		while(top && w[st[top]].y<=w[i].y)top--;
		while(top>1 && F(i,st[top-1])<=F(st[top],st[top-1]))top--;
		st[++top]=i;
	}
	for(i=0;i<m;i++)printf("%.7lf\n",Res[i]);
	return 0;
}

Subtask #1

1.0 / 1.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	92 ms	3656 KB	Output is correct
2	Correct	88 ms	3656 KB	Output is correct
3	Correct	100 ms	3656 KB	Output is correct
4	Correct	104 ms	3656 KB	Output is correct
5	Correct	48 ms	3656 KB	Output is correct
6	Correct	48 ms	3656 KB	Output is correct
7	Correct	44 ms	3656 KB	Output is correct
8	Correct	44 ms	3656 KB	Output is correct
9	Correct	52 ms	3656 KB	Output is correct
10	Correct	48 ms	3656 KB	Output is correct
11	Correct	56 ms	3656 KB	Output is correct
12	Correct	40 ms	3656 KB	Output is correct
13	Correct	56 ms	3656 KB	Output is correct
14	Correct	52 ms	3656 KB	Output is correct
15	Correct	56 ms	3656 KB	Output is correct
16	Correct	48 ms	3656 KB	Output is correct