제출 #4136

#제출 시각아이디문제언어결과실행 시간메모리
4136pl0892029Jogging (kriii1_J)C++98
0 / 1
84 ms4000 KiB
#include <cstdio> #include <algorithm> #include <cmath> using namespace std; typedef struct point { int x,y; }point; bool cmp(point a,point b) { return a.x == b.x ? a.y < b.y : a.x < b.x; } point star[100000], DEQ[100000]; int Mx[100000]; double Mans[100000]; int main() { int n, m; scanf("%d %d",&n,&m); for(int i=0;i<n;i++) { int x, y; scanf("%d %d",&x,&y); star[i].x=x; star[i].y=y; } sort(star,star+n,cmp); for(int i=0;i<m;i++) scanf("%d",Mx+i); int currentPoint = n-1; int front = 0, rear = -1; for(int i=m-1;i>=0;i--) { for( ; currentPoint >= 0 && Mx[i] < star[currentPoint].x; currentPoint--) { while( front <= rear ) { if( DEQ[rear].y <= star[currentPoint].y ) rear--; else break; } DEQ[++rear] = star[currentPoint]; } while( front < rear ) { if( (long long)DEQ[front+1].y*(DEQ[front].x-Mx[i]) <= (long long)DEQ[front].y*(DEQ[front+1].x-Mx[i]) ) { DEQ[front+1] = DEQ[front]; front++; } else break; } if( rear < front ) Mans[i] = 0; else Mans[i] = atan((double)DEQ[rear].y/(DEQ[rear].x-Mx[i])); } for(int i=0;i<m;i++) printf("%.7lf\n",Mans[i]); }
#Verdict Execution timeMemoryGrader output
Fetching results...