[기하학] BOJ 31397 - 반 나누기 (Hard)

https://www.acmicpc.net/problem/31397

문제

루타비스의 수호자, 시간술사 반반은 모든 음식을 반으로 먹는 것을 즐깁니다. 비록 후라이드 양념 반반 치킨을 먹지는 않지만, 중식은 항상 짬짜면을, 피자집에서는 항상 하프 앤 하프 피자를 주문합니다.

생일을 맞은 반반은 그의 동료인 어릿광대 피에르에게서 볼록다각형 모양의 케이크를 하나 선물받았습니다. 반반은 이 케이크를 일직선으로 한 번 잘라서 반으로 나눠 먹고 싶습니다. 특히 나눠진 후의 케이크 밑면의 면적과 둘레가 똑같도록 하고 싶습니다.

반반이 원하는 대로 케이크를 두 조각으로 나눌 수 있을까요?

입력

첫 줄에는 반반이 선물받은 케이크 밑면의 모양인 볼록다각형의 꼭짓점 개수 \(N\)이 주어집니다. \((3 \le N \le 200\,000)\) 

다음 \(N\)개의 줄의 \(i\)번째 줄에는 볼록다각형의 \(i\)번째 점의 좌표를 의미하는 두 정수 \(x_i, y_i\)가 공백으로 구분되어 주어집니다. \((-10^7 \le x_i, y_i \le 10^7)\)

꼭짓점은 다각형의 어느 한 점에서 시작해서 반시계방향으로 주어지며, 서로 다른 세 점이 한 직선 위에 있는 경우는 없습니다.

출력

첫 줄에, 케이크를 넓이와 둘레가 같은 두 도형으로 분할할 수 있다면 YES, 없다면 NO를 출력하세요.

첫 줄에 YES를 출력한 경우, 칼질을 시작하고 끝내는 두 점이 각각 \(x_j\)와 \(x_{j+1}\)의 \(\alpha : 1-\alpha\) 내분점, \(x_k\)와 \(x_{k+1}\)의 \(\beta: 1-\beta\) 내분점인 경우, 둘째 줄에 \(j\)와 \(\alpha\)를 공백으로 구분하여, 셋째 줄에 \(k\)와 \(\beta\)를 공백으로 구분하여 출력하세요. 이 때, \(x_{N+1} = x_1\)이라고 생각합니다. \((1 \le j, k \le N;\) \(0 \le \alpha, \beta \le 1)\) 

두 점을 이은 선분을 기준으로 볼록다각형을 나누었을 때, 나뉜 두 도형의 넓이와 둘레의 절대 혹은 상대 오차가 \(10^{-6}\) 이하여야 합니다.

 

Solved.ac 그랜드 아레나 #4에서 출제되었던 문제다. 나는 Division 2를 참가하여 쉬운 버전의 반 나누기를 접했었는데, 볼록 다각형에서 잘려진 서로의 넓이가 같아지는 분할선만 찾으면 되는 문제였다.

하지만, 어려운 버전으로써의 반 나누기는 이야기가 꽤 다르다. 왜냐하면 잘려진 넓이 뿐만 아니라 둘레까지 같아야 하기 때문이다(이지 버전하고 문제 본문 내용이 너무 비슷해서 어떤게 차이점이었는지 한참 헤맸다). 조건이 두개가 됨으로써 비단 단순한 이분 탐색으로 쉽게 끝나지 않는 문제가 되었다.

 

---

분할된 다각형의 넓이 구하기

먼저, 세 점의 위치가 주어졌을때 삼각형의 넓이를 구하는 함수를 정의한다.

$TriangleSize(a,b,c)=\frac{|(b-a)\times(c-a)|}{2}$

그 다음, $Lerp(Point[i], Point[i+1], \alpha)$에서 $Lerp(Point[j], Point[j+1], \beta)$까지 칼질을 끝냈을 때 잘린 방향에서 오른쪽 다각형의 넓이를 구하는 $SegmentSize(i, \alpha, j, \beta)$ 함수를 정의한다.

구간에 $Point[0]$이 포함되지 않은 경우 $(i<j)$

어떤 한 기준점과 볼록 다각형 둘레의 구간을 이루는 각각의 선분으로 이루어진 삼각형들의 넓이의 합에서 기준점과 분할선의 교차점 두 개로 이루어진 삼각형의 넓이의 합을 빼면 된다. 기준점은 볼록 다각형 내부의 어떤 점이든 가능하지만 편의상 여기서는 $Point[0]$로 하겠다.

$SegmentSize(i,\alpha, j,\beta)=\sum_{k=i+1}^{j-1} {TriangleSize(Point[0],Point[k],Point[k+1])}\\+TriangleSize(Point[0],Lerp(Point[i], Point[i+1],\alpha),Point[i+1])\\+ TriangleSize(Point[0],Point[j],Lerp(Point[j], Point[j+1],\beta))\\-TriangleSize(Point[0],Lerp(Point[i], Point[i+1], \alpha),Lerp(Point[j], Point[j+1],\beta))$

처음 데이터를 입력 받았을 때 $Point[0]$을 기준으로 모든 삼각형의 넓이에 대한 누적합을 먼저 구하면 위의 식을 $O(1)$ 시간 복잡도로 구할 수 있다.

구간에 $Point[0]$이 포함된 경우 $(i>j)$

반대쪽 분할 다각형의 넓이를 구한 후 볼록 다각형의 전체 넓이에서 빼 준다.

 

---

조건을 만족하는 분할선을 구하는 방법

볼록 다각의 둘레 위에 피봇$(Pivot_x)$을 아무렇게 하나 잡는다. 여기 예시에서는 $Point[0]$ 으로 하겠다.

그러면, 이 피봇을 지나면서 둘레가 같도록 볼록 다각형을 자르는 분할선은 유일하다. 맞은편 피봇$(Pivot_x')$은 $ Pivot_x$ 에서 볼록 다각형의 둘레의 반만큼 둘레를 지난 위치를 가진다.
분할된 두 다각형은 단면을 서로 공유하기에, 볼록 다각형의 둘레를 이분하는 분할선으로 자른 다각형은 서로 둘레가 같은 점에 의한 것이다.

여기서 오른쪽 다각형 $S_1$의 넓이를 구해 본다. 앞서 언급한 식 대로 볼록 다각형의 둘레를 지나는 두 피봇에 대한 다각형의 넓이를 구할 수 있다. 이렇게 구해진 넓이 $S_1$은 볼록 다각형의 총 넓이의 반이 될 수도 있지만(그러면 바로 정답이 나온다), 반보다 적거나 많은 경우가 대부분일 것이다.

여기서 중요한 부분은 이렇다. 다른 한 쪽 다각형의 넓이 $S_2$는 반대로 볼록 다각형의 총 넓이의 반보다 각각 많거나 적을 것이고, 그것은 $Pivot_x$를 $Pivot_x'$로 옮겨 분할선을 다시 만들었을때 오른쪽 다각형의 넓이가 되는 것이다.
그렇다는 것은, $Pivot_x$를 $Pivot_ x'$로 볼록 다각형의 둘레를 따라 이동하는 도중에 오른쪽 다각형의 넓이가 총 넓이의 반이 되는 분할선을 만들 수 있는 지점이 하나 이상 존재한다. 이런 경우 동일한 둘레와 넓이를 가지게 하는 분할선을 구하게 되는 것이다.

이는 사잇값 정리에서 그 원리를 찾을 수 있다. 연속 함수에서 구간의 두 점에서의 함숫값 사이의 값을 가지는 점은 그 구간 사이에 하나 이상 존재한다. $Pivot_x$를 이동할때 넓이가 변화하는 것을 함수 $f(x)$로 나타내었을 때, $Pivot_x$의 이동량이 0에 수렴할 경우 넓이의 변화량도 따라 0에 항상 수렴하기 때문에 함수 $f(x)$는 연속이다.

이제 이분 탐색으로 그 지점을 구할 수 있다. 물론 제시했던 것만 고려하면 사잇값 정리에 의해 넓이가 같아지는 지점이 두 개 이상 나올 수 있게 되는 셈이다. 하나냐 여러개냐에 대해서 증명을 해본 적은 없으나, 정답의 요구사항은 상기된 두 조건을 만족하는 것을 하나만 찾는 것이고, 이분 탐색은 찾고자 하는 값이 구간 안에 여러개가 있든 문제 없이 그 중에 하나를 잘 도출해 준다.

시간 복잡도는 $O(N+log\frac{L}{\epsilon}logN)$ ($L=$볼록 다각형의 길이)이다.

 

---

소스 코드

#include <bits/stdc++.h>
#define FASTIO() cin.tie(0),cout.tie(0),ios::sync_with_stdio(0)
#define PRECISION(n) cout<<fixed,cout.precision(n)

using namespace std;
using int64 = long long;

int64 xi[200000];
int64 yi[200000];
double dpsum[200001];
double spsum[200001];

double lerp(double a, double b, double t)
{
	return a + (b - a) * t;
}

double triangle_size(double ax, double ay, double bx, double by, double cx, double cy)
{
	return abs((by - ay) * (cx - bx) - (bx - ax) * (cy - by));
}

double size_segment(int n, int i, double ti, int j, double tj)
{
	int i0 = i;
	int j0 = j;
	if (i > j)
	{
		swap(i0, j0);
		swap(ti, tj);
	}
	int i1 = (i0 + 1) % n;
	int j1 = (j0 + 1) % n;
	double s = spsum[j0] - spsum[i1];
	double ix = lerp(xi[i0], xi[i1], ti);
	double iy = lerp(yi[i0], yi[i1], ti);
	double jx = lerp(xi[j0], xi[j1], tj);
	double jy = lerp(yi[j0], yi[j1], tj);
	s += triangle_size(xi[0], yi[0], ix, iy, xi[i1], yi[i1]);
	s += triangle_size(xi[0], yi[0], xi[j0], yi[j0], jx, jy);
	s -= triangle_size(xi[0], yi[0], ix, iy, jx, jy);
	return i > j ? s : spsum[n] - s;
}

tuple<int, double, int, double> get_ij(int n, double di, double dj)
{
	int i = 0;
	int j = 0;
	for (int dx = 1 << 17; dx > 0; dx >>= 1)
	{
		if (i + dx < n && dpsum[i + dx] < di)
			i += dx;
		if (j + dx < n && dpsum[j + dx] < dj)
			j += dx;
	}
	double ti = (di - dpsum[i]) / (dpsum[i + 1] - dpsum[i]);
	double tj = (dj - dpsum[j]) / (dpsum[j + 1] - dpsum[j]);

	return make_tuple(i, ti, j, tj);
}

int main()
{
	FASTIO();
	PRECISION(12);

	int n;
	cin >> n;
	for (int i = 0; i < n; ++i)
		cin >> xi[i] >> yi[i];
	for (int i = 0; i < n; ++i)
	{
		int64 dx = xi[(i + 1) % n] - xi[i];
		int64 dy = yi[(i + 1) % n] - yi[i];
		dpsum[i + 1] = dpsum[i] + sqrt(dx * dx + dy * dy);
		spsum[i + 1] = spsum[i] + triangle_size(xi[0], yi[0], xi[i], yi[i], xi[(i + 1) % n], yi[(i + 1) % n]);
	}

	double dl = 0;
	double dr = dpsum[n] * 0.5;
	auto [i, ti, j, tj] = get_ij(n, dl, dr);
	double cz = size_segment(n, i, ti, j, tj) - spsum[n] * 0.5;
	for (int k = 0; k < 100; ++k)
	{
		double dm = (dl + dr) * 0.5;
		double di = dm;
		double dj = dm + dpsum[n] * 0.5;
		if (dj >= dpsum[n])
			dj -= dpsum[n];
		tie(i, ti, j, tj) = get_ij(n, di, dj);
		double cs = size_segment(n, i, ti, j, tj) - spsum[n] * 0.5;
		if (cs * cz > 0.0)
			dl = dm;
		else
			dr = dm;
	}

	cout << "YES\n";
	cout << i + 1 << " " << ti << "\n";
	cout << j + 1 << " " << tj << "\n";
}