| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 4238 | sjw0687 | Jogging (kriii1_J) | C++98 | 0 ms | 0 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#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, int> pii;
struct Star {
int x,y;
const bool operator < (const Star rhs) {
return x != rhs.x ? x < rhs.x : y > rhs.y;
}
};
int n;
int m;
Star stars[10001];
int xRest[10000];
double answer[10000];
int minX[10000];
stack< pii > s;
int calXBoundary(Star& s1, Star& s2)
{
double a = (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( pii(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( pii(iStar-1, calXBoundary(newStar, stars[s.top().first])) );
else
s.push( pii(iStar-1, -INF) );
while(x <= s.top().second) {
s.pop();
}
iStar--;
}
answer[i] = atan( (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;
}