CSAcademy Round #33 : D. Subinterval Division

これは割とすんなり解けた。
https://csacademy.com/contest/round-33/task/subinterval-division/

問題

2次元座標上でY座標が非負の点がN個与えられる。
また、線分(0,0)-(X,0)がある。

各点に対し、線分上でN点中その点が最寄となるような部分の長さをそれぞれ求めよ。

解法

まず頂点をX座標順に並べたものをP(i)とする。
なお、同一X座標でY座標が異なるものが複数ある場合、Y座標が最小の点だけ残す(他の点はどうやっても線分中に条件を満たす領域が生じない)
Q(i)を点P(i)とP(i+1)の垂直二等分線とX軸の交点のX座標とする。

点P(i)に対し条件を満たす線分の部分はmax(Q(0)～Q(i))≦x≦min(Q(i+1)～Q(N-1))の範囲なので、それを答えればよい。
以下の解法はスライド最小値の要領でやったが、iを小さい順にQ(i)を求めてmaxを更新するのと、iを大きい順に処理してminを更新するのを計2周した方が楽かも。

ll N,D;
ll X[101010],Y[101010];
pair<pair<ll,ll>,int> P[101010];
vector<int> V;
double L[101010],R[101010];
double ret[101010];

double cross(int a,int b) {
	double MX=(X[a]+X[b])/2.0;
	double MY=(Y[a]+Y[b])/2.0;
	double DX=(Y[b]-Y[a]);
	double DY=(X[b]-X[a]);
	double r=MY/DY;
	return MX+r*DX;
}

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N>>D;
	FOR(i,N) {
		cin>>X[i]>>Y[i];
		P[i]={{X[i],Y[i]},i};
		L[i]=1e10;
		R[i]=-1e10;
	}
	sort(P,P+N);
	FOR(i,N) {
		if(V.size() && X[V.back()]==X[P[i].second]) continue;
		x=P[i].second;
		L[x]=-1e18;
		R[x]=1e18;
		double tar=-1e18;
		while(V.size()>=2) {
			int a=V[V.size()-2];
			int b=V[V.size()-1];
			
			double t1=cross(a,b);
			double t2=cross(b,x);
			
			if(t1<t2) break;
			L[b]=1e10;
			R[b]=-1e10;
			V.pop_back();
		}
		
		if(V.size()>=1) {
			R[V.back()]=L[x]=cross(V.back(),x);
		}
		V.push_back(x);
		
	}
	
	FOR(i,N) {
		if(L[i]<R[i]) ret[i]=max(0.0,min(R[i],1.0*D)-max(L[i],0.0));
		_P("%.12lf\n",ret[i]);
	}
}

まとめ

DとEで得意不得意が分かれた感じ。