제출 #4169

#제출 시각아이디문제언어결과실행 시간메모리
4169pl0892029Jogging (kriii1_J)C++98
0 / 1
100 ms4044 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 j = n-1; int front = 0, rear = -1; for(int i=m-1;i>=0;i--) { for( ; j >= 0 && Mx[i] < star[j].x; j--) { while( front <= rear ) { if( DEQ[rear].y <= star[j].y ) rear--; else break; } while( front < rear ) { if( (long long)(DEQ[rear].y-star[j].y)*(DEQ[rear-1].x-star[j].x) <= (long long)(DEQ[rear-1].y-star[j].y)*(DEQ[rear].x-star[j].x) ) { rear--; } else break; } ++rear; DEQ[rear].x = star[j].x; DEQ[rear].y = star[j].y; } 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].x = DEQ[front].x; DEQ[front+1].y = DEQ[front].y; front++; } else break; } if( rear < front ) Mans[i] = 0; else Mans[i] = atan2((double)DEQ[rear].y,(double)(DEQ[rear].x-Mx[i])); } for(int i=0;i<m;i++) printf("%.7lf\n",Mans[i]); }
#Verdict Execution timeMemoryGrader output
Fetching results...