Submission #4119

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
4119	2013-09-01T16:16:01 Z	Skeas	Jogging (kriii1_J)	C++	1 / 1	104 ms	5000 KB

J

#include <iostream>
#include <cstring>
#include <cstdio>
#include <string>
#include <sstream>
#include <vector>
#include <deque>
#include <queue>
#include <stack>
#include <set>
#include <map>
#include <algorithm>
#include <cmath>

using namespace std;

#define pii pair<int,int>
#define pb push_back
#define mp make_pair
#define f first
#define s second
#define EPS 1e-9
#define ll long long

int n,m;
int dq[100005];
int rest[100005];
pii star[100005];

int main() {
#ifdef LOCAL
	freopen("input.txt","r",stdin);
#endif
	scanf("%d%d",&n,&m);
	for(int i=0;i<n;++i) {
		int x,y; scanf("%d%d",&x,&y);
		star[i] = mp(x,y);
	} sort(star,star+n);
	int nn = 0;
	for(int i=0;i<n;++i) {
		if(nn==0) star[nn++] = star[i];
		else {
			if(star[nn-1].f == star[i].f) star[nn-1] = star[i];
			else star[nn++] = star[i];
		}
	} n = nn;
	for(int i=0;i<m;++i) scanf("%d",rest+i);

	vector<double> ans;
	int s = 0, e = 0;
	int j=n-1;
	for(int i=m-1;i>=0;--i) {
		while(j >= 0 && star[j].f > rest[i]) {
			while(s < e && star[dq[e-1]].s <= star[j].s) e--;
			while(s+1 < e &&
				(ll)(star[dq[e-1]].s-star[j].s) * (star[dq[e-2]].f-star[dq[e-1]].f) <= (ll)(star[dq[e-2]].s-star[dq[e-1]].s) * (star[dq[e-1]].f-star[j].f))
				e--;
			dq[e++] = j;
			j--;
		}
		while(s+1 < e && (ll)star[dq[e-1]].s * (star[dq[e-2]].f-rest[i])  <= (ll)star[dq[e-2]].s * (star[dq[e-1]].f-rest[i])) e--;
		if(s==e) ans.push_back(0);
		else ans.push_back(atan2(1.0*star[dq[e-1]].s,1.0*(star[dq[e-1]].f-rest[i])));
	}

	for(int i=m-1;i>=0;--i) printf("%.7lf\n",ans[i]);
}

Subtask #1

1.0 / 1.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	96 ms	5000 KB	Output is correct
2	Correct	80 ms	5000 KB	Output is correct
3	Correct	104 ms	5000 KB	Output is correct
4	Correct	100 ms	5000 KB	Output is correct
5	Correct	48 ms	4232 KB	Output is correct
6	Correct	48 ms	4232 KB	Output is correct
7	Correct	52 ms	4232 KB	Output is correct
8	Correct	52 ms	4232 KB	Output is correct
9	Correct	52 ms	4232 KB	Output is correct
10	Correct	56 ms	4232 KB	Output is correct
11	Correct	48 ms	4232 KB	Output is correct
12	Correct	48 ms	4232 KB	Output is correct
13	Correct	56 ms	4232 KB	Output is correct
14	Correct	60 ms	4232 KB	Output is correct
15	Correct	52 ms	4232 KB	Output is correct
16	Correct	56 ms	4232 KB	Output is correct