#include<stdio.h>
#include<algorithm>
#include<cmath>
#include<set>
using namespace std;
struct lin {
double a, b;
bool operator< (const lin& c) const {
if(a!=c.a)return a<c.a;
return b<c.b;
}
}ba[111111], im, dl[111111];
int dir(lin p, lin q, lin r){
double t = p.a*q.b + q.a*r.b + r.a*p.b - p.b*q.a - q.b*r.a - r.b*p.a;
if(t>0)return 1;
if(t<0)return -1;
return 0;
}
int n, m, cn;
double xs[111111], dap[111111];
set<lin> conv;
set<lin>::iterator it, a, b, lm;
int main(){
int i, j, k;
scanf("%d%d", &n, &m);
for(i=0; i<n; i++)scanf("%lf%lf", &ba[i].a, &ba[i].b);
sort(ba, ba+n);
for(i=0; i<m; i++)scanf("%lf", &xs[i]);
for(i=m-1, j=n-1; i>=0; i--){
while(j>=0){
if(xs[i]>=ba[j].a)break;
im.a=-1/ba[j].b, im.b=ba[j].a/ba[j].b, j--;
if(conv.empty()){
conv.insert(im);
continue;
}
cn=0;
it=conv.lower_bound(im), lm=conv.begin();
if(it!=lm){
a=b=it, a--, b--;
while(b!=lm){
b--;
if(dir(*b,*a,im)==1)break;
dl[cn++]=*a, a=b;
}
}
lm=conv.end(), lm--;
if(it!=conv.end()){
a=b=it;
while(b!=lm){
b++;
if(dir(im,*a,*b)==1)break;
dl[cn++]=*a, a=b;
}
}
if(it==conv.begin() || it==conv.end())conv.insert(im);
else{
a=it, a--;
if(dir(*a, im, *it)==1)conv.insert(im);
}
for(k=0; k<cn; k++)conv.erase(dl[k]);
}
if(conv.empty())dap[i]=0;
else{
a=it=conv.begin(), a++;
cn=0;
while(a!=conv.end()){
if(xs[i]*(*it).a+(*it).b > xs[i]*(*a).a+(*a).b)dl[cn++]=*it;
it=a, a++;
}
for(k=0; k<cn; k++)conv.erase(dl[k]);
it=conv.begin();
dap[i]=atan(1/(xs[i]*(*it).a+(*it).b));
}
}
for(i=0; i<m; i++)printf("%.7lf\n", dap[i]);
return 0;
}
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Execution timed out |
1000 ms |
7524 KB |
Program timed out |
| 2 |
Halted |
0 ms |
0 KB |
- |
