[기하학 / 미적분학] BOJ 34173 - PS는 풋살의 약자야

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

문제

동우는 일주일에 한 번 씩 카톡방에 풋살 ㄱ?를 보낼 정도로 풋살 악귀이다. 재우도 동우 못지않은 풋살 악귀이지만, 하늘이는 풋살을 싫어한다. 동우와 재우는 PS를 시작하려는 하늘이에게 PS는 풋살의 약자라며 매일 풋살을 하자고 한다. 하늘이는 풋살은 P가 아니라 F라고 주장하지만, 씨알도 먹히지 않자 지친 하늘이는 하나의 내기를 제안한다.

먼저 동우와 재우, 하늘이는 무한히 큰 $2$차원 평면의 풋살장에서 각각 점 $A$, $B$, $C$에 위치하고 있다. 동우는 공을 차 재우에게 패스해야 하며, 하늘이는 이 공이 재우에게 도착하기 전 공을 가로채야 한다. 하늘이는 $1$의 속력으로 일정하게 이동할 수 있고, 동우는 고정된 $v$의 속력으로 움직이는 공을 찰 수 있다. 이 공은 처음에 동우의 위치에서 출발하며, 궤적은 동우가 원하는 대로 정할 수 있다. 단, 공을 한번 차고 나서는 이를 수정할 수 없다. 수학과인 하늘이는 동우가 공을 차는 순간 공의 궤적을 계산해낼 수 있으며, 최적으로 움직여 공을 뺏으려 한다. 동우는 땅볼 패스를 좋아하므로 공을 공중으로 띄울 수 없고, 공은 $2$차원 평면에서만 움직인다고 가정한다.

만약 하늘이가 공의 위치에 도달해 패스를 가로채기 전에 재우에게 먼저 공이 도착한다면 하늘이는 내기에서 패배하고 풋살을 하러 가야 한다. 이를 피하고 싶던 하늘이는 재우에게 항상 자신이 먼저 공을 가로챌 수 있는 위치에 서 있어 달라고 부탁했다. 동우와 하늘이의 위치 $A$와 $C$, 공의 속력 $v$가 주어질 때, 항상 하늘이가 먼저 공을 가로챌 수 있도록 재우가 있을 수 있는 위치 $B$가 이루는 면적을 구해 보자. 단, 동우와 하늘이는 처음에 서로 다른 위치에 있다.

입력

첫 번째 줄에 테스트 케이스의 개수 $T(1\le T\le 10\, 000)$가 주어진다.

각 테스트 케이스의 첫 번째 줄에 동우와 하늘이의 좌표를 나타내는 정수 $x_A,y_A,x_C,y_C(1\le x_A,y_A,x_C,y_C\le 10^9)$, 공의 속력을 의미하는 정수 $v(1\le v\le 10^9)$가 공백으로 구분되어 주어진다.

처음에 동우와 하늘이는 서로 다른 위치에 있으므로, $x_A \neq x_C$ 또는 $y_A \neq y_C$이다.

출력

각 테스트 케이스 별로 한 줄에 정답을 출력한다. 만약 답이 무한하다면 -1을 대신 출력한다.

정답과의 절대/상대 오차는 $10^{-6}$까지 허용한다.

서브태스크

번호	배점	제한
1	18	$v=1$
2	82	추가적인 제한 조건 없음

 

2025년도 고려대학교 MatKor Cup에 출제되었던 문제이다. 대회 당시에 온사이트로 참가하고 있었는데, 대회에 나오는 몇 안되는 기하 문제라 최선을 다해 붙잡고 있었으나, 결국 서브태스크 일부만 통과한 채로 대회가 종료되었다.

서브태스크 1번의 경우($v=1$), 동우와 하늘이가 다른 위치에 있는 조건 하에서 재우가 있을 수 있는 영역은 항상 무한하다. 재우가 서 있을 수 있는 위치는 동우와의 거리보다 하늘이와의 거리가 가까운 점의 집합이 되고, 이는 반평면을 나타낸다.

서브태스크 1번의 경우

서브태스크 2번의 경우는 난이도가 상당히 올라간다. 이때 재우가 있을 수 있는 영역은 유한하지만, 이는 원이나 타원 형태가 아닌 별개의 식을 세워 적분을 해야하는 형태이다.

하늘이를 중심으로 시간이 지날수록 $1$만큼 반지름이 커지는 원을 생각해 보자. 이 원은 시간에 따라 하늘이가 공을 가로챌 수 있는 영역을 나타낸다고 볼 수 있다. 그리고, 동우로부터 길이가 시간당 $v$만큼 임의로 움직이는 점을 동우가 찬 공이라고 생각했을 때, 재우가 있을 수 없는 위치는 움직이는 점이 커지는 원에 포함되지 않으면서 도달할 수 있는 위치의 집합이다.

동우가 임의의 궤적으로 공을 찰 수 있는 만큼, 동우는 가능한 한 최단 경로인 직선 궤적으로 차려고 할 것이다. 만약 재우가 동우 기준으로 하늘보다 대략 앞에 있을 경우, 동우가 차게 되는 최적의 경로는 직선이다. 이때, 영역의 경계는 아폴로니우스의 원을 그린다.

재우가 동우 기준으로 하늘보다 대략 뒤에 있을 경우, 동우가 차게 되는 최적의 경로가 직선이 아닐 수도 있다. 왜냐하면, 직선으로 움직이는 점이 하늘에게 닿기 전에 커지는 원에 포함될 수 있기 때문이다. 이때, 최적의 경로는 커지는 원의 테두리를 따라 빙 둘러서 가는 궤적이 된다. 이의 경우는 Logarithmic Spiral을 그리게 된다.

재우가 오른쪽에 있을 경우 동우가 차게 되는 최적의 경로

이 두가지 경우를 나누어 영역을 각각 구하고 서로 더하는게 이 문제의 정답이 된다.

 

---

영역을 구하기에 앞서

먼저, 동우와 하늘이의 위치를 단순화시키자(WLOG). 재우가 있을 수 있는 점의 집합은 오로지 동우와 하늘이의 거리와 공의 속도에만 영향을 받으므로, 좌표계에서 동우와 하늘이의 거리 정보만 남긴 채 나머지 정보는 고려하지 않아도 된다. 이는 동우를 원점에 고정시키고 하늘이의 위치를 동우와의 거리 그대로 $x$축 상에 배치함으로써 위치를 단순하게 만들 수 있다.

 

---

아폴로니우스의 원

출처: 위키피디아 "Apollonian circles" 문서

유클리드 좌표계에 서로 다른 두 점이 있을 때, 이 두 점으로부터의 거리의 비가 $m : n$ $(m \neq n)$인 점들의 집합은 원을 나타내는 성질이 존재한다. 재우가 하늘이보다 앞에 있을 때, 동우는 직선으로 공을 차게 되므로, 영역의 테두리인 동우의 공과 하늘이가 같은 시간에 도달하게 되는 위치의 집합은 동우로부터와 하늘이로부터의 거리의 비가  $v : 1$ 인 아폴로니우스의 원이 될 것이다.

이 때, 원의 중심 $O = (\frac{lv^2}{v^2-1}, 0)$, 반지름 $r = \frac{lv}{v^2-1}$ ($l=$동우와 하늘이의 거리)

 

---

Logarithmic Spiral

출처: mathcurve.com

Logarithmic Spiral은 각도와 반지름이 지수 관계인 특수한 나선이다. 극좌표계에 나타낸 함수의 일반형은 $r=ae^{k\theta}$이다. 소라껍질, 태풍, 은하에서도 관찰할 수 있는 이 Logarithmic Spiral은 몇 가지 특수한 성질이 있다.

• 나선의 어떤 지점에서든 접선이 이루는 경사각이 $\tan\alpha=k$로 동일하다.
• 중심으로부터의 나선 길이는 $\frac{r}{\sin \alpha}$로 반지름과 선형 관계이다.
• 회전, 스케일 변환을 했을 때 주기적으로 원본과 합동이 된다.
• 기타 등 ...

아무리 확대를 해도 똑같은 모습으로 끊임없이 반복되고, 확대와 회전이 구분이 되지 않는 이 나선, 정말 신기하다. 하지만 무엇보다도, 나선 길이가 반지름과 선형 관계를 가진다는 두번째 성질은 해당 문제에 이 나선을 이용할 수 있게 해 주는 핵심적인 요소이다! 왜냐하면, 동우가 찬 공이 시간당 1만큼 커지는 원의 경계를 따라 $v$의 속도로 움직이면 $\sin \alpha = \frac{1}{v}$ 인 Logarithmic Spiral 이 궤적이 되기 때문이다.

물론, 공이 출발하는 지점은 원의 중심이 아닌 원으로부터 일정 거리($l$) 만큼 떨어져 있기 때문에, 일부 구간은 원의 테두리를 향해 최적으로 달려가는 직선 구간을 일부 포함하게 된다. 하늘이로부터 뻗어 나오는 Logarithmic Spiral이 두 사람의 거리의 비를 $v : 1$로 유지하면서 동우를 지나도록 하는 접선이 그런 구간이 된다. 나선을 회전시켜가면서 조건을 만족하는 접선이 존재하는지 확인해야한다.

하지만 신기한 사실이 하나 있다. 전에 언급하였던 아폴로니우스의 원과 동우를 지나는 접선이 위의 조건을 만족하는 접선과 항상 동일하다. 해당 접선에 맞추어 역으로 Logarithmic Spiral을 구하면 그 아폴로니우스의 원과의 교점에서의 접선 또한 서로 동일한 것을 알 수 있다. 증명도 한 적 없이 이런 사실이 튀어나와서 정말 놀랐지만, 아마 방정식을 구하면 그러한 관계가 나올 것 같다고 확신한다. 덕분에 아폴로니우스의 원과 Logarithmic Spiral의 넓이를 구하는 구간도 이 접선을 기준으로 나눌 수 있다.

Logarithmic Spiral의 구간 넓이는 $\frac{r_{to}^2-r_{from}^2}{4k}$로 구할 수 있다.

테스트 케이스 1-2

동우가 $(1, 1)$, 하늘이가 $(1, 2)$ 에 있고, 속도 $v=2$인 테스트케이스를 Desmos에서 가시화한 결과이다. 위에서 제시하였던 좌표계 단순화와 달리 하늘이 원점이 된 점 양해 부탁드립니다. (극좌표계 때문에 ...)

아폴로니우스의 원은 초록색, Logarithmic Spiral은 파란색으로 표시하였다. 동우를 지나가는 아폴로니우스의 원의 접선을 구한 후 해당 접점을 기준으로 동우를 향하는 쪽은 아폴로니우스의 원의 넓이(부채꼴 - 삼각형)를, 동우를 등지는 쪽은 Logarithmic Spiral의 영역 넓이를 $y > 0$ 에서 구한 후 이를 $2$로 곱해주면 재우의 영역의 넓이를 구할 수 있다.

 

---

소스 코드

#define _USE_MATH_DEFINES
#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;

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

	int t;
	cin >> t;
	while (t--)
	{
		long long xa, ya, xc, yc, v;
		cin >> xa >> ya >> xc >> yc >> v;
		if (v == 1)
		{
			cout << "-1\n";
			continue;
		}
		long long dx = xc - xa;
		long long dy = yc - ya;
		double l = sqrt(dx * dx + dy * dy);
		double o = v * v * l / (v * v - 1);
		double r = v * l / (v * v - 1);
		double t = sqrt(o * o - r * r) / v;
		double th = acos((o * o + r * r - v * v * t * t) / (2 * o * r));
		double ph = acos((l * l + t * t - v * v * t * t) / (2 * l * t));
		double k = 1 / sqrt(v * v - 1);
		double sa = (r * r * th - (o - l) * t * sin(ph)) / 2;
		double sb = t * t * (pow(M_E, k * (M_PI - ph) * 2) - 1) / (k * 4);
		cout << (sa + sb) * 2 << "\n";
	}
}