Submission #4171

#	Time	Username	Problem	Language	Result	Execution time	Memory
4171		pl0892029	Jogging (kriii1_J)	C++98	1 / 1	100 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 j = n-1;
	int front = 0, rear = -1;

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

		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].x = DEQ[front].x;
				DEQ[front+1].y = DEQ[front].y;
				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: 1 / 1