Codeforces #358 Div2 E. Alyona and Triangles

この解法面白いな。
http://codeforces.com/contest/682/problem/E

問題

２次元座標上にN個の格子点が与えられる。
このうち３点を選んで三角形を作るとき、その面積の最大値はS以下であることが保証される。

面積が4S以下で、これら全頂点を含むような三角形を構築せよ。

解法

N点のうち、三角形を作ったとき面積が最大となる３点をA,B,Cとしよう。
A,Bを固定したとき、A,Bを結ぶ直線からの距離がCより遠い点は存在しない（存在したら、そちらの三角形の方が面積が大きい）。
よって、A,B,C以外の頂点はCから直線ABと平行に伸ばした直線上か、それより直線AB寄りにある。
同様に、各頂点は頂点Aから直線BCと平行に伸ばした直線よりBC寄りにあり、頂点Bから直線ACと平行に伸ばした直線よりAC寄りにある。

つまり、A,B,Cをそれぞれ３辺の中点となる三角形を考えると、各頂点はこの三角形に含まれる。
また、この三角形の面積はABCの４倍なので、4S以下であることは明らかである。
よってこの三角形は条件を満たす。

面積最大の三角形は、凸包を求めたうえで、頂点Aを総当たりし、尺取法の要領で頂点Bを動かしながら、ABに対し三角形の面積を最大化できるCを求めていけばO(N^2)で出来る。

const ll EPS=0;
template<class C> C veccross(pair<C,C> p1,pair<C,C> p2,pair<C,C> p3) {
	p3.first-=p1.first;p2.first-=p1.first;
	p3.second-=p1.second;p2.second-=p1.second;
	return p3.first*p2.second-p2.first*p3.second;
}

template<class C> vector<int> convex_hull(vector< pair<C, C> >& vp) {
	vector<pair<pair<C, C>, int> > sorted;
	vector<int> res;
	int i,k=0,rb;
	
	if(vp.size()<=2) {
		if(vp.size()>=1) res.push_back(0);
		if(vp.size()>=2 && vp[0]!=vp[1]) res.push_back(1);
		return res;
	}
	
	FOR(i,vp.size()) sorted.push_back(make_pair(vp[i],i));
	sort(sorted.begin(),sorted.end());
	
	res.resize(vp.size()*2);
	/* bottom */
	FOR(i,vp.size()) {
		while(k>1 && veccross(vp[res[k-2]],vp[res[k-1]],sorted[i].first)<=-EPS) k--;
		res[k++]=sorted[i].second;
	}
	/* top */
	for(rb=k, i=vp.size()-2;i>=0;i--) {
		while(k>rb && veccross(vp[res[k-2]],vp[res[k-1]],sorted[i].first)<=-EPS) k--;
		res[k++]=sorted[i].second;
	}
	res.resize(k-1);
	return res;
}

int N;
ll S;
ll ma=0;
int id[3];
vector<pair<ll,ll>> P,R;

ll area(int a,int b,int c) {
	ll bx=P[b].first-P[a].first;
	ll by=P[b].second-P[a].second;
	ll cx=P[c].first-P[a].first;
	ll cy=P[c].second-P[a].second;
	return abs(bx*cy-by*cx);
	
}

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N>>S;
	FOR(i,N) {
		cin>>x>>y;
		R.push_back({x,y});
	}
	auto VV=convex_hull(R);
	FORR(r,VV) P.push_back(R[r]);
	N=P.size();
	for(i=0;i<N;i++) {
		for(j=i+1,k=j+1;j<N;j++) {
			k=min(N-1,max(j,k));
			while(k+1<N && area(i,j,k+1)>=area(i,j,k)) k++;
			if(area(i,j,k)>ma) {
				ma=area(i,j,k);
				id[0]=i;
				id[1]=j;
				id[2]=k;
			}
		}
	}
	
	cout<<(P[id[0]].first+P[id[2]].first-P[id[1]].first)<<" "<<(P[id[0]].second+P[id[2]].second-P[id[1]].second)<<endl;
	cout<<(P[id[1]].first+P[id[2]].first-P[id[0]].first)<<" "<<(P[id[1]].second+P[id[2]].second-P[id[0]].second)<<endl;
	cout<<(P[id[0]].first+P[id[1]].first-P[id[2]].first)<<" "<<(P[id[0]].second+P[id[1]].second-P[id[2]].second)<<endl;
	
}

まとめ

ちょっと前ゼルダの伝説をプレイしたのに、なぜこの形状に気が付かなかったのか。