Submission #16943

#	Time	Username	Problem	Language	Result	Execution time	Memory
16943		gs14004	Jogging (kriii1_J)	C++14	1 / 1	124 ms	4300 KiB

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 / 1