Submission #4171

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
4171	2013-09-03T03:18:32 Z	pl0892029	Jogging (kriii1_J)	C++	1 / 1	100 ms	4000 KB

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.0 / 1.0

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