BOJ 9583 Easy Geometry

문제 링크입니다.

문제 요약

주어진 볼록다각형 내부에 포함되며 넓이가 가장 큰 축평행 직사각형을 찾으세요.

풀이

직사각형의 두 $x$좌표가 고정된 상황을 먼저 고려합시다. 주어진 다각형이 볼록하므로, 다각형 내부의 점들을 이어 만든 다각형은 항상 전체 다각형 내부에 포함됩니다. 그러니 양쪽 $y$좌표를 되는 대로 최대한 밀어내는 게 유리하겠네요. 볼록 다각형을 이루는 위쪽 껍질과 아래쪽 껍질에 대해 각각 $x$좌표에 대한 이분 탐색을 수행하면, 특정 $x$좌표에서 볼록 다각형에 포함되는 점의 $y$좌표의 최댓값/최솟값을 구할 수 있습니다. 이때 직사각형의 최대 넓이는 두 $x$좌표에 대한 $y$좌표 구간의 교집합을 써서 구하면 됩니다.

원 안의 직사각형을 잠깐 생각해 봅시다. 직사각형의 폭을 0에서부터 증가시키면, 직사각형의 넓이는 점점 증가하다가 이내 다시 감소하게 될 것입니다. 구체적으로 직사각형의 폭에 따른 직사각형의 넓이가 볼록함수고, 이는 원 대신 볼록 다각형을 갖다 놔도 비슷하게 성립합니다. 따라서 폭에 대한 삼분 탐색으로 답을 구할 수 있음을 확인할 수 있어요.

고정된 폭에 대한 최선의 $x$좌표를 찾아내 봅시다. 마찬가지로 양 껍질이 볼록하기 때문에, $x$좌표에 따른 직사각형의 넓이가 볼록 함수임을 알 수 있습니다. 따라서 $x$좌표에 대해 삼분 탐색을 하면 고정된 두 $x$좌표에 대한 최대 직사각형 넓이를 구해 문제를 해결할 수 있고, 이는 처음에 우리가 고려했던 문제입니다!

해서, 삼분 탐색 안에서 삼분 탐색 안에서 이분 탐색하는 코드를 구현하면 AC를 받을 수 있습니다.

코드

제 볼록 껍질 구현체가 up_hull 이랑 down_hull 을 반대로 구하고 있었더라고요? 귀찮아서 따로 수정은 안 했고, 그래서 up_hull 이 $y$좌표가 작은 쪽 껍질입니다.

#include<bits/stdc++.h>
#define x first
#define y second
using namespace std;
using ld = long double;
using pii = pair<int, int>;
using pld = pair<ld, ld>;
ld mx, my, Mx, My, opt_xl;

pld operator- (pld a, pld b){
	return {a.x-b.x, a.y-b.y};
}
inline ld dist(pld a, pld b){
	return (a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y);
}
inline auto outer(pld a, pld b){
	return a.x*b.y-b.x*a.y;
}
inline auto ccw(pld a, pld b, pld c){
	auto ret = outer(b-a,c-a);
	return (ret<0)-(ret>0);
}
inline auto cccw(pld a, pld b, pld c, pld d){
	d = d-(c-b);
	return ccw(a, b, d);
}

vector<pld> hull, up_hull, down_hull;

void decomp(){ //wtf i reversed it??
	sort(hull.begin(), hull.end());
	for(int i = 0; i < hull.size(); i++){
		while(up_hull.size() >= 2 && ccw(up_hull[up_hull.size()-2], up_hull[up_hull.size()-1], hull[i]) >= 0){
			up_hull.pop_back();
		}
		up_hull.push_back(hull[i]);
		while(down_hull.size() >= 2 && ccw(down_hull[down_hull.size()-2], down_hull[down_hull.size()-1], hull[i]) <= 0){
			down_hull.pop_back();
		}
		down_hull.push_back(hull[i]);
	}
	return;
}

pld gety(ld x){
	int uidx = int(lower_bound(up_hull.begin()+1, up_hull.end(), pld(x,0))-up_hull.begin());
	int didx = int(lower_bound(down_hull.begin()+1, down_hull.end(), pld(x,0))-down_hull.begin());
	return {up_hull[uidx-1].y+(x-up_hull[uidx-1].x)/(up_hull[uidx].x-up_hull[uidx-1].x)*(up_hull[uidx].y-up_hull[uidx-1].y),
			down_hull[didx-1].y+(x-down_hull[didx-1].x)/(down_hull[didx].x-down_hull[didx-1].x)*(down_hull[didx].y-down_hull[didx-1].y)
	};
}

ld getwx(ld xl, ld xr){
	auto [ld, lu] = gety(xl);
	auto [rd, ru] = gety(xr);
	return (xr-xl)*(min(lu, ru)-max(ld, rd));
}

ld getw(ld w){
	ld xl = mx, xr = Mx-w;
	for(int xstep = 0; xstep < 100; xstep++){
		ld xm1 = (xl+xl+xr)/3, xm2 = (xl+xr+xr)/3;
		if(getwx(xm1, xm1+w) > getwx(xm2, xm2+w)) xr = xm2;
		else xl = xm1;
	}
	opt_xl = xl;
	return getwx(xl, xl+w);
}

int main(){
	cin.tie(0);cout.tie(0);ios::sync_with_stdio(false);
	int n; cin >> n; hull.resize(n);
	for(int i = n-1; i >= 0; i--) cin >> hull[i].x >> hull[i].y;
	mx = Mx = hull[0].x; my = My = hull[0].y;
	for(int i = 1; i < n; i++){
		mx = min(mx, hull[i].x); Mx = max(Mx, hull[i].x);
		my = min(my, hull[i].y); My = max(My, hull[i].y);
	}
	decomp(); ld wl = 0, wr = Mx-mx;
	for(int wstep = 0; wstep < 100; wstep++){
		ld wm1 = (wl+wl+wr)/3, wm2 = (wl+wr+wr)/3;
		if(getw(wm1) > getw(wm2)) wr = wm2;
		else wl = wm1;
	}
	cout << fixed << setprecision(12);
	auto [ld, lu] = gety(opt_xl);
	auto [rd, ru] = gety(opt_xl+wl);
	cout << opt_xl << ' ' << max(ld, rd) << ' ' << opt_xl+wl << ' ' << min(lu, ru);
}