Submission #16943

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
16943	2015-11-01T14:38:21 Z	gs14004	Jogging (kriii1_J)	C++14	1 / 1	124 ms	4300 KB

J

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <math.h>
#include <limits.h>
#include <stack>
#include <queue>
#include <map>
#include <set>
#include <algorithm>
#include <string>
#include <functional>
#include <vector>
#include <numeric>
#include <deque>
#include <utility>
#include <bitset>
#include <iostream>
using namespace std;
typedef long long lint;
typedef long double llf;
typedef pair<int, int> pi;

int n, q;
pi a[100005];
int pos[100005];
double ret[100005];

vector<pi> hull;

int ccw(pi a, pi b, pi c){
	int dx1 = b.first - a.first;
	int dy1 = b.second - a.second;
	int dx2 = c.first - a.first;
	int dy2 = c.second - a.second;
	lint tmp = 1ll * dx1 * dy2 - 1ll * dy1 * dx2;
	if(tmp == 0) return 0;
	return tmp > 0 ? 1 : -1;
}

int main(){
	scanf("%d %d",&n,&q);
	for(int i=0; i<n; i++){
		scanf("%d %d",&a[i].first, &a[i].second);
	}
	sort(a, a+n);
	for(int i=0; i<q; i++){
		scanf("%d",&pos[i]);
	}
	int p = n-1;
	for(int i=q-1; i>=0; i--){
		while(p >= 0 && a[p].first > pos[i]){
			while(hull.size() >= 2 && ccw(hull[hull.size()-2], hull.back(), a[p]) <= 0){
				hull.pop_back();
			}
			hull.push_back(a[p]);
			p--;
		}
		if(hull.empty()) continue;
		int s = 0, e = hull.size() - 1;
		while(s != e){
			int m = (s+e)/2;
			if(ccw(pi(pos[i],0),hull[m], hull[m+1]) <= 0){
				e = m;
			}
			else s = m+1;
		}
		ret[i] = atan2(hull[s].second, hull[s].first - pos[i]);
	}
	for(int i=0; i<q; i++){
		printf("%.7f\n",ret[i]);
	}
}

Subtask #1

1.0 / 1.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	124 ms	4044 KB	Output is correct
2	Correct	83 ms	4300 KB	Output is correct
3	Correct	83 ms	3912 KB	Output is correct
4	Correct	104 ms	3912 KB	Output is correct
5	Correct	0 ms	3912 KB	Output is correct
6	Correct	43 ms	3912 KB	Output is correct
7	Correct	39 ms	3912 KB	Output is correct
8	Correct	55 ms	3912 KB	Output is correct
9	Correct	57 ms	3912 KB	Output is correct
10	Correct	50 ms	3912 KB	Output is correct
11	Correct	52 ms	3912 KB	Output is correct
12	Correct	59 ms	3912 KB	Output is correct
13	Correct	54 ms	3912 KB	Output is correct
14	Correct	51 ms	3912 KB	Output is correct
15	Correct	65 ms	3912 KB	Output is correct
16	Correct	56 ms	3912 KB	Output is correct