oj.uz

답안 #4119

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
4119 2013-09-01T16:16:01 Z Skeas Jogging (kriii1_J) C++
1 / 1
 104 ms 5000 KB 
#include <iostream>
#include <cstring>
#include <cstdio>
#include <string>
#include <sstream>
#include <vector>
#include <deque>
#include <queue>
#include <stack>
#include <set>
#include <map>
#include <algorithm>
#include <cmath>

using namespace std;

#define pii pair<int,int>
#define pb push_back
#define mp make_pair
#define f first
#define s second
#define EPS 1e-9
#define ll long long

int n,m;
int dq[100005];
int rest[100005];
pii star[100005];

int main() {
#ifdef LOCAL
	freopen("input.txt","r",stdin);
#endif
	scanf("%d%d",&n,&m);
	for(int i=0;i<n;++i) {
		int x,y; scanf("%d%d",&x,&y);
		star[i] = mp(x,y);
	} sort(star,star+n);
	int nn = 0;
	for(int i=0;i<n;++i) {
		if(nn==0) star[nn++] = star[i];
		else {
			if(star[nn-1].f == star[i].f) star[nn-1] = star[i];
			else star[nn++] = star[i];
		}
	} n = nn;
	for(int i=0;i<m;++i) scanf("%d",rest+i);

	vector<double> ans;
	int s = 0, e = 0;
	int j=n-1;
	for(int i=m-1;i>=0;--i) {
		while(j >= 0 && star[j].f > rest[i]) {
			while(s < e && star[dq[e-1]].s <= star[j].s) e--;
			while(s+1 < e &&
				(ll)(star[dq[e-1]].s-star[j].s) * (star[dq[e-2]].f-star[dq[e-1]].f) <= (ll)(star[dq[e-2]].s-star[dq[e-1]].s) * (star[dq[e-1]].f-star[j].f))
				e--;
			dq[e++] = j;
			j--;
		}
		while(s+1 < e && (ll)star[dq[e-1]].s * (star[dq[e-2]].f-rest[i])  <= (ll)star[dq[e-2]].s * (star[dq[e-1]].f-rest[i])) e--;
		if(s==e) ans.push_back(0);
		else ans.push_back(atan2(1.0*star[dq[e-1]].s,1.0*(star[dq[e-1]].f-rest[i])));
	}

	for(int i=m-1;i>=0;--i) printf("%.7lf\n",ans[i]);
}

Subtask #1
1.0 / 1.0

# 결과 실행 시간 메모리 Grader output
1 Correct 96 ms 5000 KB Output is correct
2 Correct 80 ms 5000 KB Output is correct
3 Correct 104 ms 5000 KB Output is correct
4 Correct 100 ms 5000 KB Output is correct
5 Correct 48 ms 4232 KB Output is correct
6 Correct 48 ms 4232 KB Output is correct
7 Correct 52 ms 4232 KB Output is correct
8 Correct 52 ms 4232 KB Output is correct
9 Correct 52 ms 4232 KB Output is correct
10 Correct 56 ms 4232 KB Output is correct
11 Correct 48 ms 4232 KB Output is correct
12 Correct 48 ms 4232 KB Output is correct
13 Correct 56 ms 4232 KB Output is correct
14 Correct 60 ms 4232 KB Output is correct
15 Correct 52 ms 4232 KB Output is correct
16 Correct 56 ms 4232 KB Output is correct