Submission #3610

#	Time	Username	Problem	Language	Result	Execution time	Memory
3610		imsifile	Jogging (kriii1_J)	C++98	0 / 1	1000 ms	7524 KiB

J

#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;
}

• Subtask 1: 0 / 1