FII Code Round #1 : E. Sugarel’s Garden

久しぶりのCSA。
https://csacademy.com/contest/fii-code-2019-round-1/task/Sugarel-s-Garden/

問題

２次元座標上でN個の点が与えられる。
このうち４つの点を選び四角形を作る。
四角形は凸でなくてもよいが、辺同士が交差してはいけない。

このような図形のうち、他の点をちょうどM個囲うもののうち、面積の最小値を求めよ。

解法

仮に、任意の三角形内の頂点数がすでに求められていたとする。

四角形ABCDが仮に凹でも、２つの対角線ACとBDのどちらかは四角形内にある。
そこで、ACが必ず四角形にあると仮定し、A・Cを総当たりしよう。
その際、直線ACの両側においてB,Dの候補をそれぞれ総当たりする。
まずBを総当たりし、ABC内の頂点数および面積を求めて、囲う頂点数に対する面積の最小値を求めよう。
次にDを同様に総当たりし、ABCとADCの囲う頂点数の和がMとなるようなものの最小値を求めればよい。

さて、残るは三角形内の頂点数を列挙することである。
愚直に考えるとO(N^4)かかるが、これをO(N^3)で求めよう。
まず各線分ABを考える。ここでBはAよりX座標が大きいとする。
ここでf(AB) := 線分ABの下にある頂点数、とする。ここで下にある、とはX座標がAとBの間にあり、Y座標が線分ABより下にあるものとする。
f(AB)はA,Bを総当たりしてもO(N^3)で済む。

次に三角形ABCを考える。g(ABC) := 三角形ABC内の頂点数、とする。
X座標が小さい順にA,B,Cとする。

• Bが線分ACの上部にある場合、g(ABC) = f(AB)+f(BC)-f(AC)
• Bが線分ACの下部にある場合、g(ABC) = f(AC)-f(AB)-f(BC)-1

これでg(ABC)をO(N^3)で列挙できる。

int N,M;
ll X[303],Y[303];
vector<vector<ll>> P;
int under[303][303];
int num[303][303][303];

int right(int i,int j,int k) { // k is right i->j
	return (X[k]-X[i])*(Y[j]-Y[i])-(Y[k]-Y[i])*(X[j]-X[i])>0;
}

ll area(int i,int j,int k) {
	return abs((X[k]-X[i])*(Y[j]-Y[i])-(Y[k]-Y[i])*(X[j]-X[i]));
}


void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N>>M;
	FOR(i,N) {
		cin>>X[i]>>Y[i];
		P.push_back({X[i],Y[i],i});
	}
	sort(ALL(P));
	FOR(i,N) X[i]=P[i][0], Y[i]=P[i][1];
	
	FOR(j,N) FOR(i,j) for(k=i+1;k<j;k++) under[i][j]+=right(i,j,k);
	FOR(i,N) for(j=i+1;j<N;j++) for(k=j+1;k<N;k++) {
		if(right(i,k,j)) num[i][j][k]=under[i][k]-under[i][j]-under[j][k]-1;
		else num[i][j][k]=under[i][j]+under[j][k]-under[i][k];
		
		num[i][k][j]=num[j][i][k]=num[j][k][i]=num[k][i][j]=num[k][j][i]=num[i][j][k];
	}
	
	ll S=1LL<<60;
	FOR(i,N) for(j=i+1;j<N;j++) {
		ll lef[404];
		FOR(k,N+1) lef[k]=1LL<<60;
		FOR(k,N) if(k!=i&&j!=k&&right(i,j,k)==0) lef[num[i][j][k]]=min(lef[num[i][j][k]],area(i,j,k));
		FOR(k,N) if(k!=i&&j!=k&&right(i,j,k)==1&&num[i][j][k]<=M) S=min(S,area(i,j,k)+lef[M-num[i][j][k]]);
	}
	
	if(S%2==0) {
		cout<<S/2<<".0"<<endl;
	}
	else {
		cout<<S/2<<".5"<<endl;
	}
	
	
	
}

まとめ

本番はg(ABC)が高速に求められず唸ってたのに、こんな簡単に求められるのか…。