oj.uz

답안 #16943

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
16943 2015-11-01T14:38:21 Z gs14004 Jogging (kriii1_J) C++14
1 / 1
 124 ms 4300 KB 
#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

# 결과 실행 시간 메모리 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