Submission #4244

#	Time	Username	Problem	Language	Result	Execution time	Memory
4244		sjw0687	Jogging (kriii1_J)	C++98	0 / 1	548 ms	5448 KiB

J

#include <cstdio>
#include <iostream>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <climits>
#include <algorithm>
#include <utility>
#include <string>
#include <vector>
#include <list>
#include <map>
#include <set>
#include <deque>
#include <queue>
#include <stack>
#include <bitset>
using namespace std;

const int INF = INT_MAX / 2;
typedef pair<int, double> pid;

struct Star {
	int x,y;

	bool operator < (const Star rhs) const {
		return x != rhs.x ? x < rhs.x : y > rhs.y;
	}
};

int n;
int m;
Star stars[100001];
int xRest[100000];
double answer[100000];

stack< pid > s;

double calXBoundary(Star& s1, Star& s2)
{
	double a = (double) (s2.y - s1.y) / (s2.x - s1.x);
	double b = s1.y - a * s1.x;

	return -b/a;
}

int main(void)
{
	cin >> n >> m;
	for(int i=0; i<n; i++) {
		cin >> stars[i].x >> stars[i].y;
	}
	stars[n].x = 100000001; stars[n].y = 0;
	for(int i=0; i<m; i++)
		cin >> xRest[i];
	sort(stars, stars+n);

	int iStar = n;
	s.push( pid(n, -INF) );
	for(int i=m-1; i>=0; i--) {
		int& x = xRest[i];

		while(x <= s.top().second)
			s.pop();

		while(iStar > 0 && x < stars[iStar-1].x) {
			Star& newStar = stars[iStar-1];
			while(!s.empty() && newStar.y >= stars[s.top().first].y) {
				s.pop();
			}

			if( !s.empty() )
				s.push( pid(iStar-1, calXBoundary(newStar, stars[s.top().first])) );
			else
				s.push( pid(iStar-1, -INF) );
			while(x <= s.top().second)
				s.pop();

			iStar--;
		}

		answer[i] = atan2( (double)stars[s.top().first].y, (stars[s.top().first].x - x) );
	}

	for(int i=0; i<m; i++) {
		cout.precision(7); cout.setf(ios::fixed);
		cout << answer[i] << endl;
	}
	
	return 0;
}

• Subtask 1: 0 / 1