Submission #4136

#	Time	Username	Problem	Language	Result	Execution time	Memory
4136		pl0892029	Jogging (kriii1_J)	C++98	0 / 1	84 ms	4000 KiB

J

#include <cstdio>
#include <algorithm>
#include <cmath>

using namespace std;

typedef struct point {
    int x,y;
}point;

bool cmp(point a,point b) {
    return a.x == b.x ? a.y < b.y : a.x < b.x;
}

point star[100000], DEQ[100000];
int Mx[100000];
double Mans[100000];

int main() {
    int n, m;	
	scanf("%d %d",&n,&m);
	for(int i=0;i<n;i++) {
		int x, y;
		scanf("%d %d",&x,&y);
			
		star[i].x=x;
        star[i].y=y;
	}

	sort(star,star+n,cmp);

	for(int i=0;i<m;i++)
		scanf("%d",Mx+i);

	int currentPoint = n-1;
	int front = 0, rear = -1;

	for(int i=m-1;i>=0;i--) {
		for( ; currentPoint >= 0 && Mx[i] < star[currentPoint].x; currentPoint--) {
			while( front <= rear ) {
				if( DEQ[rear].y <= star[currentPoint].y )
					rear--;
				else
					break;
			}
				
			DEQ[++rear] = star[currentPoint];
		}
		while( front < rear ) {
			if( (long long)DEQ[front+1].y*(DEQ[front].x-Mx[i]) <= (long long)DEQ[front].y*(DEQ[front+1].x-Mx[i]) ) {
				DEQ[front+1] = DEQ[front];
				front++;
			}
			else
				break;
		}
			
		if( rear < front )
			Mans[i] = 0;
		else
			Mans[i] = atan((double)DEQ[rear].y/(DEQ[rear].x-Mx[i]));
	}

	for(int i=0;i<m;i++)
		printf("%.7lf\n",Mans[i]);
}

• Subtask 1: 0 / 1