어떤 문제인가?

두 원이 서로 겹치는 부분의 넓이를 구하는 문제.

시행착오 횟수

4번

관찰

1. 두 원의 관계에 따라 넓이가 달라진다. 어떤 관계에 있는지 파악하는 것이 핵심이다.
2. 반드시 각도를 파악해야 문제를 해결할 수 있다. 수치 계산을 해야 하기 때문이다.

1차 시도 : 구상

처음에는 삼각함수만으로 미지의 길이를 나타내려 했으나, 불가능함을 깨달았다. 각도를 알지 못하는 이상 삼각함수를 이용한 풀이는 불가능했다.

두 원이 서로 만나는 교점을 직접 구하고 이들의 중점을 구하려고 했으나 연립방정식 해결이 좀 까다로운 편이었다.

그래서 두 원의 교점을 지나는 직선의 방정식(공통현의 방정식)을 세우고, 이에 수직인 직선의 방정식을 이용해 두 직선의 교점을 구하려고 했다.

그런데, 굳이 수직인 직선을 구할 필요도 없이 공통현의 방정식과 두 원의 중심과의 거리를 구하면 되지 않을까?
그 생각까지 든 이후에, 나는 바로 수식을 세우고 코드를 짰다.

우선 공통현의 방정식이다.

점과 직선 사이의 거리이다.

두 원 사이의 관계는 다음과 같다.
1. 겹치는 부분이 아예 없거나,
2. 일부만 겹치거나,
3. 한 원이 다른 한 원 안에 완전히 들어가거나.

3가지 경우가 있으며 이들 중
1. 겹치는 부분이 없다면 넓이는 $0$이다.
2. 한 원이 다른 한 원 안에 들어간다면 $\pi r^2$이다.
3. 일부만 겹치는 경우에는, 넓이 $S$는 다음과 같다.

$d$는 원 중심점간 거리, $D_{n}$

2차 시도 : WA

아차. 3자리 소수점까지만 표시해야 하는데 원 안에 작은 원이 완전히 들어간 경우에 대해서 그렇게 표현하지 않았다.

3차 시도 : WA

다음은 그 당시 코드다.

#include <stdio.h>
#include <math.h>

void s(double* x, double* y) {
	double t = *x;
	*x=*y;
	*y=t;
}

double a(double x) { if(x<0) return -x; return x; }

int main()
{
	double x1,y1,r1,x2,y2,r2,d,d1,d2,A,B,C,t1,t2;
	scanf("%lf%lf%lf%lf%lf%lf",&x1,&y1,&r1,&x2,&y2,&r2);
	d=sqrt(pow(x2-x1,2)+pow(y2-y1,2));
	if(x2>x1) s(&x1,&x2);
	if(y2>y1) s(&y1,&y2);
	if(r2>r1) s(&r1,&r2);
	if(r1>=d+r2) printf("%.3f",3.1415926*r2*r2);
	else if(d>=r1+r2) printf("0.000");
	else {
	    A=2*(x1-x2);
	    B=2*(y1-y2);
	    C= x2*x2-x1*x1+y2*y2-y1*y1+r1*r1-r2*r2;
	    d1 = a(A*x1+B*y1+C)/sqrt(A*A+B*B);
	    d2 = a(A*x2+B*y2+C)/sqrt(A*A+B*B);
	    t1=acos(d1/r1);
	    t2=acos(d2/r2);
	    if(d>=r1) printf("%.3f",r1*r1*t1+r2*r2*t2-r2*sin(t2)*d2-r1*sin(t1)*d1);
	    else printf("%.3f",r1*r1*t1-r1*sin(t1)*d1+r2*r2*(3.1415926-t2)+r2*sin(t2)*d2);
	}
}

틀렸을 당시 뭐가 문제인지 전혀 갈피를 잡을 수 없었다. 게다가 다음 날에 중요한 일이 있어 몸 상태를 유지해야 했지만, 새벽 1시가 다 되어서도 문제를 붙잡고 있었다.

문제 풀이에 너무 집착하다가 일을 그르칠 수 있을 것 같아서, 나는 결국 답안을 봤다. 웹에서 본 답은 따로 아래에 적을 예정이다. 내 접근방식으로 끝내 풀었으니까.

4차 시도 : AC

어떤 문제였는지 결국 알아냈다. 1차 시도: 구상에 쓰여져 있는걸 본 사람은 알아냈을지도 모르는데, 다음날에 일어나자마자 든 생각이 있었다.

$r_{1} \leq D$

머릿속으로 그림을 그려보니 정말 그 경우만 남는다는 확신이 생겼고, 그 생각을 바로 코드에 적용했다. 그리고 맞았다.

#include <stdio.h>
#include <math.h>

void s(double* x, double* y) {
	double t = *x;
	*x=*y;
	*y=t;
}

double a(double x) { if(x<0) return -x; return x; }

int main()
{
	double x1,y1,r1,x2,y2,r2,d,d1,d2,A,B,C,t1,t2;
	scanf("%lf%lf%lf%lf%lf%lf",&x1,&y1,&r1,&x2,&y2,&r2);
	d=sqrt(pow(x2-x1,2)+pow(y2-y1,2));
	if(r2>r1) {
    	s(&x1,&x2);
    	s(&y1,&y2);
	    s(&r1,&r2);
	}
	if(r1>=d+r2) printf("%.3f",3.1415926*r2*r2);
	else if(d>=r1+r2) printf("0.000");
	else {
	    A=2*(x1-x2);
	    B=2*(y1-y2);
	    C= x2*x2-x1*x1+y2*y2-y1*y1+r1*r1-r2*r2;
	    d1 = a(A*x1+B*y1+C)/sqrt(A*A+B*B);
	    d2 = a(A*x2+B*y2+C)/sqrt(A*A+B*B);
	    t1=acos(d1/r1);
	    t2=acos(d2/r2);
	    if(d>=d1) printf("%.3f",r1*r1*t1+r2*r2*t2-r2*sin(t2)*d2-r1*sin(t1)*d1);
	    else printf("%.3f",r1*r1*t1-r1*sin(t1)*d1+r2*r2*(3.1415926-t2)+r2*sin(t2)*d2);
	}
}

범위를 잘못 잡은게 문제였다. 어찌되었건 내 접근방식이 틀린게 아니라는 것이 증명되었으니 다행이다.

번외 : 제2 코사인법칙

다시 되돌아가서, 3차 시도때 결국 답안을 봤었다고 했다.
제2 코사인법칙을 사용한 적이 거의 없었기에 나는 문제를 보자마자 그러한 공식을 이용하는 접근방식이 떠오르지 않았다. 쉽게 말해 까먹어서 몰랐다.

다음은 제2 코사인법칙에 대한 공식이다. 설명은 나중에 시간이 날 때 #알고리즘-개념 시리즈에 올릴 예정이다.

삼각형 $\text{ABC}$가 주어지고, 각 $\text{A, B, C}$의 대변을 $a,\;b,\;c$

그리하여, 이를 이용해 어떠한 각의 크기를 구하는 법은,

이를 코드에 적용하면, 다음처럼 된다.

#include <stdio.h>
#include <math.h>

void s(double* x, double* y) {
	double t = *x;
	*x=*y;
	*y=t;
}

double a(double x) { if(x<0) return -x; return x; }

int main()
{
	double x1,y1,r1,x2,y2,r2,d,t1,t2,s1,s2;
	scanf("%lf%lf%lf%lf%lf%lf",&x1,&y1,&r1,&x2,&y2,&r2);
	d=sqrt(pow(x2-x1,2)+pow(y2-y1,2));
	if(r2>r1) {
		s(&x1,&x2);
		s(&y1,&y2);
		s(&r1,&r2);
	}
	if(r1>=d+r2) printf("%.3f",3.1415926*r2*r2);
	else if(d>=r1+r2) printf("0.000");
	else {
	    t1=acos((r1*r1+d*d-r2*r2)/(2*r1*d));
	    t2=acos((r2*r2+d*d-r1*r1)/(2*r2*d));
	    s1=(r1*r1*2*t1)/2-(r1*r1*sin(2*t1)/2);
	    s2=(r2*r2*2*t2)/2-(r2*r2*sin(2*t2)/2);
	    printf("%.3lf",s1+s2);
	}
}

답안은 여기에서 참고하였다.
-> https://mangu.tistory.com/m/14

번외 2 : 작은 수의 정밀성

문제를 풀 때 PI 값으로 3.1415까지만 넣은 적이 있었는데, 자꾸만 답이 608.366이 아닌 608.345로 나와서 왜 이러지하고 당황한 적이 있었다.

문제를 풀면서 깨우친 것은, 정확성을 위해서는 최대한 자세하게 적어야 한다는 것이다. 단 한자리 수의 차이가 엄청난 차이를 만들어낼 수 있음을 배웠다.

한줄평

고등학교 때 배운 기하 문제가 생각난다. 그 느낌으로 풀었고, 시간이 좀 걸리긴 했지만 까먹었던 제2코사인 법칙도 다시 배웠고, 작은 수를 연산할 때의 요령도 얻어갔으니 그것으로 만족한다.