Submission #4242

#TimeUsernameProblemLanguageResultExecution timeMemory
4242sjw0687Jogging (kriii1_J)C++98
0 / 1
12 ms2132 KiB
#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; bool operator < (const Star rhs) const { 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] = 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; }
#Verdict Execution timeMemoryGrader output
Fetching results...