[C++ 백준 풀이][Diamond II] 17441번 : 파리채 만들기 (그린 정리, Green's Theorem)

이 포스트에서는 프로그래밍 문제 사이트 백준 Online Judge의 17441번 : '파리채 만들기' 문제의 풀이 코드와 해설을 다루고 있습니다.

 

문제의 난이도는 Solved.ac 기준 Diamond II이며, 문제를 풀이하기 위해 미적분학II의 그린 정리에 대해 알고 있으면 좋습니다.

 

 

17441번 : 파리채 만들기

 

문제를 요약하면, 주어진 다각형 내의 두 점 사이 거리의 제곱에 대한 평균값을 출력하는 문제입니다.

다각형은 단순다각형이며, 반시계 방향으로 꼭짓점들의 좌표가 주어지기 때문에 Convex Hull 알고리즘의 사용은 생략해도 됩니다.

 

이 문제는 풀이 코드를 먼저 본다고 해서 이해할 수가 없는 문제이므로, 풀이를 먼저 하고 코드를 정리하겠습니다.

저도 미적분학II를 충분히 배웠지만 손 뗀지 2년이 다 되어가서 다른 분의 풀이 아이디어(https://xy-plane.tistory.com/13)를 충분히 참고하여 풀이하였습니다.

 

참고로 풀이 과정에서, 식 생략 없이 모든 식을 처음부터 끝까지 다 정리하였습니다.

 

 

 

먼저 파리채의 비용은(문제에서도 나왔지만) 원의 넓이에 넓이 당 비용을 곱하여 d^2임을 알 수 있습니다.

그렇다면 결론적으로는 E(d^2)을 구하면 됩니다.

다각형 내 좌표가 주어진 두 점 사이의 거리의 제곱은 위와 같이 되고, 또 dxdy = dA로 나타낼 수 있기 때문에 다각형의 면적을 A라고 할 때 두 점을 선택할 확률은 (dA1/A)*(dA2/A)가 됩니다.

따라서 우리는 4중 적분으로 이루어진 마지막 식을 계산하면 답을 얻을 수 있습니다.

 

 

 

1/A^2은 밖으로 빼주고, 나머지 식을 정리해보면 2번째 줄의 식과 같이 됩니다.

각 항에 대해서 따로 계산을 해보면, 위와 같이 정리되고 최종적으로 최대한 정리한 식은 가장 아랫줄의 식과 같이 됩니다.

이제 빨간색으로 표시한 1, 2, 3번의 식에 대해 그린 정리를 사용하여 면적분을 선적분으로 치환할 것입니다.

 

 

 

Green's Theorem의 정의는 위와 같고, 이 그린 정리를 1번 식에 먼저 적용해보겠습니다. (그린 정리에 대해 더 알아볼 필요 없이 그냥 저 정의된 식을 사용하기만 하면 됩니다. 물론 그린 정리의 증명이나 그린 정리의 확장이 궁금하다면 더 찾아보시는 것도 좋습니다.)

그러면 Q와 P에 대한 적절한 식을 위처럼 찾을 수 있고, 따라서 선적분으로 치환이 된 모습을 볼 수 있습니다.

 

 

 

문제에서 주어진 도형은, 폐곡선임과 동시에 다각형이기 때문에 우리는 각 변을 하나의 구간으로 만들어 그 구간은 일차식으로 표현할 수 있습니다.

따라서 시그마로 각 변에 대한 번호를 잡아주고, 적분식에서 x항에 dy가 붙어있고 y항에 dx가 붙어있기 때문에 f(x)dx, f(y)dy와 같은 형태로 만들어주기 위해 하나를 치환해주어야 합니다.

그런데 위에서 말했듯 다각형이기 때문에 각 선분을 일차식으로 표현할 수 있고, dx와 dy는 더욱 간단한 형태가 됩니다.

따라서 이 dx와 dy에 식을 대입하여, f(x)dx와 f(y)dy꼴로 바꾸어줄 수 있습니다.

 

 

 

위에서 구한 dx와 dy 식을 대입해보면, 그냥 x^3dx만 계산해주면 됨을 확인할 수 있습니다.

대입하면 위와 같이 되고, 정리하면 식이 조금 복잡하기는 하지만 a^4-b^4 꼴의 식이 a-b로 약분이 되므로 빨간색 식 정도까지는 정리해줄 수 있습니다. (물론 정리 안하고 바로 코드에 때려넣어도 상관없습니다.)

 

 

 

지금까지 1번 식에 대해 그린 정리를 적용하였으므로, 이제 2번 식에도 그린 정리를 사용해보겠습니다.

2번 식과 3번 식은 그 형태가 훨씬 간단하기 때문에(심지어 P = 0) 같은 원리로 풀이하면 더 간단하게 식을 구할 수 있습니다.

따라서 위의 빨간색 식을 구할 수 있습니다.

 

 

 

마찬가지 방법으로 3번 식에도 그린 정리를 사용할 수 있지만 3번 식은 2번 식과 x, y만 바뀐 형태이므로 변수만 바꿔서 식을 구할 수 있습니다.

 

 

 

결론적으로 E(d^2) 식을 구했고, 각 빨간색 부분의 면적분 자리에 시그마 합으로 치환한 식을 대입하여 계산만 해주면 됩니다.

(여기서는 설명을 생략했지만, 넓이의 경우에는 벡터의 외적을 활용하여 계산이 가능합니다. (식 참고))

 

 

#include <cstdio>
#include <vector>
using namespace std;
 
struct Point { double x, y; };
vector<Point> Points;
 
double Cross(Point A, Point B, Point C) {
    return A.x*(B.y-C.y) + B.x*(C.y-A.y) + C.x*(A.y-B.y);
}
 
int main() {
    int N;
    double Area = 0, Val1 = 0, Val2 = 0, Val3 = 0, Ans;
    scanf("%d", &N);
    Points.resize(N);
    for(int i=0; i<N; i++) scanf("%lf %lf", &Points[i].x, &Points[i].y);
    for(int i=0; i<N-1; i++) Area += Cross(Points[0], Points[i], Points[i+1])/2;
    for(int i=0; i<N; i++) {
        double xi = Points[i].x, xi1 = Points[(i+1)%N].x;
        double yi = Points[i].y, yi1 = Points[(i+1)%N].y;
        Val1 += ((yi1-yi)*(xi*xi*xi + xi*xi*xi1 + xi*xi1*xi1 + xi1*xi1*xi1)
                 -(xi1-xi)*(yi*yi*yi + yi*yi*yi1 + yi*yi1*yi1 + yi1*yi1*yi1))/12;
        Val2 += (yi1-yi)*(xi*xi + xi*xi1 + xi1*xi1)/6;
        Val3 += (xi1-xi)*(yi*yi + yi*yi1 + yi1*yi1)/6;
    }
    Ans = 2/(Area*Area) * (Area*Val1 - Val2*Val2 - Val3*Val3);
    printf("%.10lf", Ans);
}
 

 

풀이 코드는 위와 같고, 그저 위에서 구한 식의 계산 과정만 구현되어 있는 것입니다.

따라서 풀이 코드보다도 풀이 식을 이해하는 것이 메인이라고 볼 수 있습니다.

 

 

 

확인해보면 위와 같이 정답 처리를 받을 수 있습니다.