[백준][9374] 감시 카메라

문제는 다음과 같다.

 

1. 문제 내용 정리

- 문제에서는 볼록 다각형이 주어진다. 

- 각 좌표는 반시계방향으로 주어진다.

- 카메라의 위치는 처음 나오는 두 좌표의 중점(첫 선분의 중점)에 위치한다.

- 카메라가 볼수 있는 각도는 카메라가 설치된 변의 수직 기준, 좌우로 45도 각도만큼 볼수 있다.

- 전체 넓이의 카메라가 볼수 있는 넓이의 비율을 출력하여야한다.

 

2. 해결 발상

1) 카메라의 위치를 (0,0)으로 변경할 수 있도록, 모든 점을 평행이동한다. (모든 좌표에서, 카메라의 위치를 뺀다.)

2) 카메라가 위치하는 변의 벡터를 x성분, 그에 수직하는 벡터를 y성분으로 하여 행렬 연산을 진행한다. (그 결과, 첫 변은 x축 위에 존재하며, y>=0의 위치에 크기와 방향만 바뀐 도형이 그려진다.

3) 차례로 y=x, y=-x와 만나는 점을 구한다.

4) 구한 점을 바탕으로, 카메라가 볼수 있는 도형의 넓이, 전체 넓이를 신발끈 정리를 통해 구한다.

5) 결과를 출력한다.

 

3. 최종 구현 코드

#include <bits/stdc++.h>

using namespace std;
using ll = long long;

long double getArea(vector<array<double, 2>> points)  {
    long double result = 0L;
    for(int i = 0; i < points.size(); i++) {
        result += points[i % points.size()][0] * points[(i+1) % points.size()][1];
        result -= points[i % points.size()][1] * points[(i+1) % points.size()][0];
    }

    return abs(result);
}

void run() {
    
    int n;
    cin >> n;
    vector<array<int, 2>> points(n);

    for(int i = 0; i < n; i++) {
        cin >> points[i][0] >> points[i][1];
        points[i][0] *= 2;
        points[i][1] *= 2;
    }

    array<int, 2> camera = {(points[0][0] + points[1][0]) / 2, (points[0][1] + points[1][1]) / 2};

    for(int i = 0; i < n; i++) {
        for(int j = 0; j < 2; j++) {
            points[i][j] -= camera[j];
        }
    }

    int g = gcd(points[1][0], points[1][1]);

    vector<array<int, 2>> base_vector = {
        {(points[1][0]) / g, (points[1][1]) / g},
        {(- points[1][1]) / g, (points[1][0]) / g},
    };

    vector<array<double, 2>> modified_points(n);
    vector<array<double, 2>> watch_points = {{0,0}};

    for(int i = 0; i < n; i++) {
        modified_points[i][0] = points[i][0] * base_vector[0][0] + points[i][1] * base_vector[0][1];
        modified_points[i][1] = points[i][0] * base_vector[1][0] + points[i][1] * base_vector[1][1];
    }

    bool is_found_upper_high = false; // y = x
    bool is_found_upper_low  = false; // y = -x

    for(int i = 1; i < n; i++) {
        double x1 = modified_points[i % n][0];
        double y1 = modified_points[i % n][1];
        double x2 = modified_points[(i+1) % n][0];
        double y2 = modified_points[(i+1) % n][1];

        double x_result1 = (double)((y2-y1)*x1 - y1*(x2-x1)) / (double)(y2-y1 +x1 - x2);
        double y_result1 = x_result1;
        double x_result2 = (double)((y2-y1)*x1 - y1*(x2-x1)) / (double)(y2-y1 -x1 + x2);
        double y_result2 = -x_result2;
        if(!is_found_upper_high) {
            is_found_upper_high = ((x1 <= x_result1 && x_result1<= x2) || (x2 <= x_result1 && x_result1<= x1)) && ((y1 <= y_result1 && y_result1 <= y2) || (y2 <= y_result1 && y_result1 <= y1));
            if(is_found_upper_high) {
                watch_points.push_back({x_result1, y_result1});
            }
        }
        if(!is_found_upper_low && is_found_upper_high) {
            watch_points.push_back({x1, y1});

            is_found_upper_low = ((x1 <= x_result2 && x_result2<= x2) || (x2 <= x_result2 && x_result2<= x1)) && ((y1 <= y_result2 && y_result2 <= y2) || (y2 <= y_result2 && y_result2 <= y1));
            if(is_found_upper_low) {
                watch_points.push_back({x_result2, y_result2});
            }
        }
        
    }

    long double total_area = getArea(modified_points);
    long double watch_area = getArea(watch_points);

    cout.precision(10);

    
    cout << watch_area / total_area << "\n";


}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);

    int testcase;
    cin >> testcase;
    while(testcase--) {
        run();
    }
}

 

4. 해결 아이디어 발상의 이유

- 카메라의 위치를 (0,0)으로 평행이동한후, 첫변을 x축위에 존재할 수 있도록 한다. 그 이유는, 행렬 연산을 하면, 도형의 상대적 위치는 그대로 유지한채, 크기, 방향, 비율만 교체할 수 있다. 이는 그저, 첫변을 x축으로 하여, 좌표를 다시 표현하는 과정이다.

- 카메라의 위치를 0,0으로 하고, 해당 행렬연산을 진행하면, 어렵게, 각 변의 45도인 직선을 따로 구하는 것이 아닌, 변경된 도형에서 y=x, y=-x와 교점만 찾아내어 문제의 조건을 만족시킬 수 있다. 그 까닭은, x축이 첫 변이기 때문에, 카메라의 위치가 (0,0)이기 때문에, (0,0)을 지나며, x축에 각각 45도 각도인 y=x와 y=-x를 사용할 수 있다.

- 행렬 연산을 진행할때에는, 카메라에서 두번째 방향을 향하는 벡터를 x성분, 그에 수직하는 성분을 y성분으로 하여 진행하였는데, 이때, y성분은 도형 내부에 들어있는 수직인 벡터로 한다. 이를 사용하여 행렬 연산을 진행하면, 앞서 말한바와 같이, 도형은 y>=0 위에 존재하게 된다.

- 코드상에 x_result, y_result로 나와있는게 있는데, x_result1은, 첫번째점(x1,y1)과 두번째점(x2,y2)를 지나는 직선과 y=x의 교점을 지나는 x좌표이고, x_result2는 y=-x와 만나는 교점이다. 두 직선의 교점은 직접 계산한 뒤, 코드에 바로 적용하였다.

- watch_points라는 벡터가 코드상에 존재한다. watch_points는 카메라가 실제로 볼수 있는 좌표를 저장한 벡터이다.

- watch_points는, y=x와의 교점이 나오기 전까지는 카메라가 볼수 없으니 나머지 점을 버리고, y=x와의 교점이 발생할시, 해당점을 벡터에 추가한다. 이후, 도형의 각 점을 벡터에 포함하다가, y=-x와의 교점이 발생시, 그 이후 점은 볼수 없으니 그만 두는 것으로 한다. 이때, y=x를 무조건적으로 먼저 나온다고 할 수 있는 까닭은, 입력의 좌표가 항상 반시계방향으로 주어진다고 문제에서 주어져있으며, 앞서 설명했듯, y>=0의 위치에 도형이 존재하기 때문이다.

- watch_points 벡터에 좌표를 넣을때, if문을 두번 연속하여 사용하고 있는데, if, elseif를 사용하지 않은 까닭은 한 선분에 두 교점이 모두 존재할 수 있기 때문이다. 추후에도 설명하겠지만, 이때문에 지속적으로 문제에서 "틀렸습니다"를 받은것이기 때문에, 다시한번 집고 넘어가도록 하겠다.

5. 소스코드 제출

https://www.acmicpc.net/status?problem_id=9374&user_id=skydream10

 

6. 각 소스코드 제출별 변경사항

1) 103250735:

    - 기본 발상을 토대로 코드 작성

2) 103251446:

    - 불필요한 for문 제거

    - 문제에 10^(-6)의 오차까지 허용한다고 했기 때문에 소수 10째 자리까지 출력할 수 있도록 변경

3) 103252973

    - 디버그용(테스트하던 중에 그냥 올려봄)

4) 103430710

    - modified_points는 double로 처리하여야하지만, int로 처리하고 있었기에 double로 수정

5) 103604144

    - 103252973를 수정하여, modified_points 값을 처리할 때 int로 처리하도록 돌아감.

    - x좌표만으로 다각형내의 점인지 판단하던 것을 y좌표까지 추가.(x좌표만 판별할시, y축에 평행한 직선에서 오류 발생 반례 확인)

6) 103604432

    - modified_points값 double로 판단.

    - 코드상 오류 수정(x좌표 판단과 y좌표 판단이 별개로 이루어져 and 연산 하여야하지만, x좌표 판단부분을 묵지 않은 코드 확인)

7) 103604616

    - getArea(넓이를 구하는 함수)에서 안정성을 위해 double을 long double로 변환

8) 103604841(해결 完)

    - 한개의 선분에서 y=x, y=-x 모두 판별 가능하도록 변경(한 개의 선분에서 y=x를 판단하여, 접점이 있을 경우, y=-x를 판단하지 않아 한 선분 위에 두 개의 접점이 한 선분위에 있을 경우, 오류 발생하는 반례 확인)