oj.uz

Submission #19201

# Submission time Handle Problem Language Result Execution time Memory
19201 2016-02-20T06:18:31 Z cki86201 Jogging (kriii1_J) C++
1 / 1
 226 ms 4248 KB 
#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;
}

Subtask #1
1.0 / 1.0

# Verdict Execution time Memory Grader output
1 Correct 226 ms 3992 KB Output is correct
2 Correct 204 ms 4248 KB Output is correct
3 Correct 108 ms 3860 KB Output is correct
4 Correct 127 ms 3860 KB Output is correct
5 Correct 91 ms 3860 KB Output is correct
6 Correct 82 ms 3860 KB Output is correct
7 Correct 54 ms 3860 KB Output is correct
8 Correct 58 ms 3860 KB Output is correct
9 Correct 60 ms 3860 KB Output is correct
10 Correct 60 ms 3860 KB Output is correct
11 Correct 63 ms 3860 KB Output is correct
12 Correct 65 ms 3860 KB Output is correct
13 Correct 74 ms 3860 KB Output is correct
14 Correct 79 ms 3860 KB Output is correct
15 Correct 65 ms 3860 KB Output is correct
16 Correct 70 ms 3860 KB Output is correct