Codeforces #660 Div2 E. Uncle Bogdan and Projections

比較的簡単だった回。
https://codeforces.com/contest/1388/problem/E

問題

2次元座標上に、N個の線分がある。
各線分はX軸に平行で、Y座標が正であり、かつ互いに交差しない。

ここで、Y座標が負であるようなベクトルの向きに平行な光線を照射し、X軸上にN個の線分を射影することを考える。
射影された全区間に対し、X座標の最大値から最小値を引いたものの最小値を求めよ。

解法

ConvexHullTrickを使い、平行な光線に対する各線分のX座標の最大値の最大値と、最小値の最小値を求められるようにしよう。
こうすれば、光線の傾きが決まれば、「射影された全区間に対し、X座標の最大値から最小値を引いたものの」が高速に求められるようになる。

光線の傾きについては、2つの線分の両端が交差する値をO(N^2)通り列挙すればよい。

int N;
int XL[2020],XR[2020],Y[2020];
ll LP[2020],RP[2020],Q[2020];
int A[2020];
double mi;

vector<pair<ll,ll>> P;
int rem[4040404];

template<typename V> struct ConvexHull {
	deque<pair<V,V>> Q;
	V calc(pair<V,V> p, V x) {
		return p.first*x+p.second;
	}
	int dodo(pair<V,V> A,pair<V,V> B, pair<V,V> C) {
		return ((B.second-C.second)*(B.first-A.first)<=(A.second-B.second)*(C.first-B.first));
	}
	void add(V a, V b) { // add ax+b
		if(Q.size() && Q.back().first==a) {
			//aが同じ場合
			if(b<=Q.back().second) return; //minの場合
			Q.pop_back();
		}
		Q.push_back({a,b});
		int v;
		while((v=Q.size())>=3 && dodo(Q[v-3],Q[v-2],Q[v-1]))
			Q[v-2]=Q[v-1], Q.pop_back();
	}
	void add(vector<pair<V,V>> v) {
		sort(v.begin(),v.end());
		for(auto r=v.begin();r!=v.end();r++) add(r->first,r->second);
	}
	
	
	V query(V x) {
		int L=-1,R=Q.size()-1;
		while(R-L>1) {
			int M=(L+R)/2;
			(0^((calc(Q[M],x)<=calc(Q[M+1],x)))?L:R)=M;
		}
		return calc(Q[R],x);
	}
};
ConvexHull<double> CHL,CHR;

bool cmp(pair<ll,ll> L,pair<ll,ll> R) {
	return L.first*R.second<R.first*L.second;
}

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N;
	FOR(i,N) cin>>XL[i]>>XR[i]>>Y[i];
	
	P.push_back({0,1});
	FOR(i,N) FOR(j,N) if(Y[i]<Y[j]) {
		P.push_back({XR[j]-XL[i],Y[j]-Y[i]});
		P.push_back({XL[j]-XR[i],Y[j]-Y[i]});
	}
	
	sort(ALL(P),cmp);
	P.erase(unique(ALL(P)),P.end());
	FOR(i,N) FOR(j,N) if(Y[i]<Y[j]) {
		pair<ll,ll> a={XR[j]-XL[i],Y[j]-Y[i]};
		x=lower_bound(ALL(P),a,cmp)-P.begin();
		a={XL[j]-XR[i],Y[j]-Y[i]};
		y=lower_bound(ALL(P),a,cmp)-P.begin();
		rem[y+1]++;
		rem[x]--;
	}
	
	vector<pair<double,double>> LC,RC;
	FOR(i,N) {
		LC.push_back({Y[i],-XL[i]});
		RC.push_back({-Y[i],XR[i]});
	}
	CHL.add(LC);
	CHR.add(RC);
	
	mi=1e19;
	FOR(i,P.size()) {
		if(i) rem[i]+=rem[i-1];
		if(rem[i]) continue;
		double a=1.0*P[i].first/P[i].second;
		mi=min(mi,CHR.query(a)+CHL.query(a));
	}
	
	
	
	_P("%.12lf\n",(double)mi);
}

まとめ

本番3.9sでかなりギリギリだった。