제출 #19201

#제출 시각아이디문제언어결과실행 시간메모리
19201cki86201Jogging (kriii1_J)C++98
1 / 1
226 ms4248 KiB
#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;
    }
    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]){
            while(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;
}
#Verdict Execution timeMemoryGrader output
Fetching results...