yukicoder : No.2438 Double Least Square

なるほど。
https://yukicoder.me/problems/no/2438

問題

正整数Hと、2次元座標上第1象限内にあるN個の点の座標が与えられる。
(0,0)を通る直線f(x)=axと、(0,H)を通る直線g(x)=bx+Hを考える。a,bは任意の値を取れるとする。

各点(x,y)のコストは、min((f(x)-y)^2,(g(x)-y)^2)であるとする。
a,bを最適に設定したとき、総コストの最小値を求めよ。

解法

各点について、どちらの直線に対しminimumを取るかを定めてしまえば、a,bの値は最小二乗法の要領で求めることができる。

まずf(x)とg(x)が、N点のx座標の最大値までの範囲で交差しない場合を考える。
(0,H/2)と各点を通る線の傾きを考えると、これらの傾きが小さい点はf(x)、大きい点はg(x)との最小値を取った方がよくなる。
そこで、f(x)とg(x)に割り振る点の境目を総当たりしていけばよい。

次に、f(x)とg(x)が交差するケースを考えると、交差する点のX座標x'を境界に、f(x)とg(x)のどちらに割り振るべきかが反転する。
x'を総当たりしつつ、上記同様にf(x)とg(x)に割り振る点の境目を総当たりしていけばよい。

int N,H;
int X[2020],Y[2020];
vector<pair<double,int>> Vs;
vector<int> Xs;

double hoge(ll xx,ll xy,ll yy) {
	if(xx==0) return 0;
	double a=1.0*xy/xx;
	return (yy-2*a*xy+a*a*xx);
	
}

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N>>H;
	FOR(i,N) {
		cin>>X[i]>>Y[i];
		double a=(Y[i]-H/2.0)/X[i];
		Vs.push_back({a,i});
		Xs.push_back(X[i]);
	}
	Xs.push_back(505);
	double ret=1e9;
	sort(ALL(Vs));
	FORR(px,Xs) {
		ll YY[2]={},XY[2]={},XX[2]={};
		FOR(i,N) {
			if(X[i]<px) {
				XX[1]+=(X[i]*X[i]);
				XY[1]+=(X[i]*(-H+Y[i]));
				YY[1]+=((-H+Y[i])*(-H+Y[i]));
			}
			else {
				XX[0]+=(X[i]*X[i]);
				XY[0]+=(X[i]*Y[i]);
				YY[0]+=(Y[i]*Y[i]);
			}
		}
		ret=min(ret,hoge(XX[0],XY[0],YY[0])+hoge(XX[1],XY[1],YY[1]));
		FORR2(d,i,Vs) {
			if(X[i]<px) {
				XX[0]+=(X[i]*X[i]);
				XY[0]+=(X[i]*Y[i]);
				YY[0]+=(Y[i]*Y[i]);
				XX[1]-=(X[i]*X[i]);
				XY[1]-=(X[i]*(-H+Y[i]));
				YY[1]-=((-H+Y[i])*(-H+Y[i]));
			}
			else {
				XX[0]-=(X[i]*X[i]);
				XY[0]-=(X[i]*Y[i]);
				YY[0]-=(Y[i]*Y[i]);
				XX[1]+=(X[i]*X[i]);
				XY[1]+=(X[i]*(-H+Y[i]));
				YY[1]+=((-H+Y[i])*(-H+Y[i]));
			}
			ret=min(ret,hoge(XX[0],XY[0],YY[0])+hoge(XX[1],XY[1],YY[1]));
		}
	}
	_P("%.12lf\n",ret);
	
	
}

まとめ

わかってしまえばそこまで難しくないな。