| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 4067 | ainta | 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<stdio.h>
#include<algorithm>
#define INF 1e9
using namespace std;
struct point{
int x,y;
bool operator <(const point &p)const{
return x<p.x;
}
}w[100001];
int X[100001],n,m,i,st[100001],top;
double Res[100001];
double F(int a,int b){
if(w[a].y>=w[b].y)return -INF;
double A=w[a].y;
A=A*(w[b].x-w[a].x);
A=A/(w[b].y-w[a].y);
A=w[a].x-A;
return A;
}
int main()
{
scanf("%d%d",&n,&m);
for(i=0;i<n;i++){
scanf("%d%d",&w[i].x,&w[i].y);
}
sort(w,w+n);
for(i=0;i<m;i++)scanf("%d",&X[i]);
int pv=m-1;
for(i=n-1;i>=-1;i--){
while(i==-1 || X[pv]>=w[i].x){
while(top>1 && F(st[top],st[top-1])>=X[pv])top--;
if(top==0)Res[pv]=0;
else{
Res[pv]=atan2(w[st[top]].y,w[st[top]].x-X[pv]);
}
pv--;
if(pv<0)break;
}
if(pv<0)break;
while(top>1 && F(i,st[top-1])<=F(st[top],st[top]-1))top--;
if(!top || F(i,st[top])<X[pv])st[++top]=i;
}
for(i=0;i<m;i++)printf("%.7lf\n",Res[i]);
return 0;
}