Submission #4072

#	Time	Username	Problem	Language	Result	Execution time	Memory
4072		ainta	Jogging (kriii1_J)	C++98	1 / 1	104 ms	3656 KiB

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 / 1