Submission #19188

#	Time	Username	Problem	Language	Result	Execution time	Memory
19188		cki86201	Jogging (kriii1_J)	C++98	0 / 1	207 ms	4632 KiB

J

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <memory.h>
#include <math.h>
#include <assert.h>
#include <stack>
#include <queue>
#include <map>
#include <set>
#include <string>
#include <algorithm>
#include <iostream>
#include <functional>

using namespace std;
typedef long long ll;
typedef pair<int, int> Pi;
#define Fi first
#define Se second
#define pb(x) push_back(x)
#define sz(x) (int)x.size()
#define rep(i,n) for(int i=0;i<n;i++)
#define all(x) x.begin(),x.end()

struct point{
	int x, y;
	bool operator<(const point &l)const{
		return x == l.x ? y > l.y : x > l.x;
	}
	point operator-(const point &l)const{
		return {x-l.x, y-l.y};
	}
	int operator*(const point &l)const{
		//cross
		ll tmp = (ll)x * l.y - (ll)y * l.x;
		return tmp > 0 ? 1 : (tmp == 0 ? 0 : -1);
	}
}p[100010];
int C[100010];
double ans[100010];

double get(int x, point &a){
	return atan((double)a.y / (a.x - x));
}

int main(){
	int n, m; scanf("%d%d", &n, &m);
	rep(i, n){
		int x, y;
		scanf("%d%d", &x, &y);
		p[i] = {x, y};
	}
	sort(p, p+n);
	rep(i, m)scanf("%d", C+i);
	vector <point> v;
	for(int i=m-1, j=0;i>=0;i--){
		while(j != n && p[j].x > C[i]){
			if(sz(v) >= 2 && (v.back() - v[sz(v)-2]) * (p[j] - v.back()) <= 0)v.pop_back();
			v.pb(p[j]);
			++j;
		}
		if(sz(v) == 0)continue;
		int low = 0, high = sz(v) - 2;
		double res = get(C[i], v[0]);
		while(low <= high){
			int mid = (low + high) >> 1;
			double a = get(C[i], v[mid]);
			double b = get(C[i], v[mid+1]);
			if(a < b)res = b, low = mid + 1;
			else high = mid - 1;
		}
		ans[i] = res;
	}
	rep(i, m)printf("%.7f\n", ans[i]);
	return 0;
}

• Subtask 1: 0 / 1