Submission #4135

#	Time	Username	Problem	Language	Result	Execution time	Memory
4135		pl0892029	Jogging (kriii1_J)	C++98	0 / 1	88 ms	4660 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);
		
		point star[100000];
		
		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( (double)DEQ[front+1].y/(DEQ[front+1].x-Mx[i]) <= (double)DEQ[front].y/(DEQ[front].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