[algospot] FOSSIL

문제링크 입니다

🚀 [FOSSIL] 문제 😊😊😊😊😊

봄마다 비염 환자들을 괴롭히는 꽃가루는 종종 과거의 기후 변화를 추적하는 데 유용하게 사용됩니다. 퇴적층에서 발견되는 꽃가루 화석을 통해 각 지방의 기후가 어땠는지 확인할 수 있기 때문입니다. 아마추어 고생물학자인 후연이는 서로 다른 환경에서 자라는 두 종류의 꽃 A 와 B 에 대해 각각의 꽃가루가 발견된 위치들을 지도상에 다음 그림과 같이 표시해 보았습니다.

이 지도에서는 y 좌표가 증가하는 방향이 북쪽, x 좌표가 증가하는 방향이 동쪽입니다. 후연이는 각 꽃의 서식지를 예측하기 위해, 해당 화석이 발견된 위치들을 감싸는 최소의 볼록 다각형을 위 그림에 표시된 것과 같이 구했습니다. 이 다각형들을 볼록 껍질(convex hull) 이라고 부릅니다.

후연이는 이 두 개의 볼록 껍질이 서로 겹치는 부분은 과거에 온도 변화가 심했을 것이라는 가설을 세웠습니다. 이 부분이 얼마나 넓은지 확인하기 위해 이 겹치는 부분 중 남북 방향 폭이 가장 넓은 위치를 찾고자 합니다. 예를 들어 위 그림에서는 점선으로 표현된 곳에서 남북 방향의 폭이 가장 넓습니다.

두 개의 볼록 껍질이 주어질 때 겹치는 부분의 남북 최대 폭을 계산하는 프로그램을 작성하세요.

🔑 [풀이]

문제를 보면 다각형의 교집합을 구하여 남북 최대 폭을 계산하는 문제처럼 보이지만, 쉽게 해결하는 방법이 책에 설명되어 있습니다.
먼저 두 볼록 다각형의 교집합은 항상 볼록 다각형이라는 점을 알고, x값이 감소하는 윗껍질과 x값이 증가하는 아래 껍질로 나눕니다.(시계반대방향으로 주어지기 때문)
윗껍질의 선분좌표를 두 다각형 관계없이 upper 벡터에 저장하고 아래껍질을 lower 벡터에 저장합니다. (decompose 함수에서 구현)
그 다음 upper 벡터의 최소값과 lower 벡터의 최대값을 구합니다(남북 최대 폭, vertical 함수에서 구현).
마지막으로 이전에 배웠던 삼분검색을 통하여 x값을 기준으로 폭의 최대값을 찾고 출력합니다.(겹치지 않는다면 0반환)

자세한 내용은 코드 참고 바랍니다.

ps. 처음에 이해가 잘 되지않아 그림이 잘 설명되어 있는 다음 블로그를 참고 하였습니다. 참고 블로그

⌨️ 입력

입력의 첫 줄에는 테스트 케이스의 수 c (c <= 50) 가 주어집니다. 각 테스트 케이스는 세 줄로 주어집니다. 첫 줄에는 두 볼록 껍질에 포함된 점의 수 n 과 m (1 <= n,m <= 100) 이 주어집니다. 다음 줄에는 2n 개의 실수로 첫 번째 볼록 껍질에 포함된 점의 좌표 (x,y) 가 시계 반대 방향 순서대로 주어집니다. 그 다음 줄에는 2m 개의 실수로 두 번째 볼록 껍질에 포함된 점의 좌표 (x,y) 가 시계 반대 방향 순서대로 주어집니다. 각 좌표는 [0,100] 범위의 실수로, 소수점 밑 최대 2자리까지만 주어집니다.

한 테스트 케이스에는 같은 점이 두 번 들어오지 않으며, 한 직선 위에 있는 세 점이 주어지는 일도 없습니다. 주어진 두 다각형의 모든 내각은 180도 미만입니다.

🖥 출력

각 테스트 케이스마다 한 줄에, 두 볼록 껍질이 겹치는 부분의 남북 최대 폭을 출력합니다. 만약 두 볼록 껍질이 겹치지 않을 경우 0 을 출력합니다. 정답과 10-7 이하의 절대/상대 오차를 갖는 답은 정답으로 인정됩니다.

🖱 입력 예제

2
5 5
35.74 35.85 69.64 50.00 73.52 82.55 43.50 92.22 17.67 76.18
16.47 8.02 60.98 14.62 66.80 37.74 45.89 67.22 13.04 55.19
4 3
73.84 11.41 71.61 32.72 39.87 38.84 22.41 17.87
75.13 51.64 47.72 87.34 15.97 64.56

💻 출력 예제

27.6529680365
0.000000

💎 전체 코드는 다음과 같습니다.

//
//  FOSSIL.cpp
//  AALGGO
//
//  Created by inhyeok on 2021/11/11.
//

#include <iostream>
#include <fstream>
#include <vector>
#include <utility>
#include <algorithm>

using namespace std;
ifstream fin("FOSSIL.txt");
struct point{
    double x,y;
};

int n; // 첫번째 다각형의 좌표 수
int m; // 두번째 다각형의 좌표 수
vector<point> hull1, hull2; // 다각형의 좌표
vector<pair<point, point> > upper, lower; // 윗껍질과 아래껍질 다각형
void Clear();
double minX(const vector<point> &hull){
    double result = hull[0].x;
    for(int i = 1; i<hull.size(); i++){
        result = min(result, hull[i].x);
    }
    return result;
}
double maxX(const vector<point> &hull){
    double result = hull[0].x;
    for(int i = 1; i<hull.size(); i++){
        result = max(result, hull[i].x);
    }
    return result;
}

// 윗 껍질과 아래껍질로 나누고 저장
void decompose(const vector<point> &hull){
    int n = hull.size();
    for(int i=0; i<n; i++){
        // hull이 반시계 방향이므로
        // x 가 증가할 때 -> 아래 껍질에 속하는것
        if(hull[i].x < hull[(i+1)%n].x){ // 모듈러 n을 해주는 이유는 맨 끝 좌표에서 원점으로 가는 경우때문
            lower.push_back(make_pair(hull[i], hull[(i+1)%n]));
        }
        // x 가 감소 -> 위 껍질에 속함
        else if(hull[i].x > hull[(i+1)%n].x){
            upper.push_back(make_pair(hull[i],hull[(i+1)%n]));
        }
    }
}

// [a.x, b.x] 구간안에 있는지를 판별한다.
bool between(const point &a,const point &b, const double x){
    return (a.x <= x <= b.x) || (b.x <= x <= a.x);
}

// 선분이 과 x값이 교차하는 점의 y값을 반환한다
double at(const point &a, const point &b, double x){
    double inclination = (b.y-a.y)/(b.x-a.x);
    double y_intercept = a.y-(inclination*a.x);
    return inclination*x + y_intercept;
}

// x 좌표가 주어질 때 잘린 부분의 길이를 반환
double vertical(double x){
    // minUp -> 윗껍질 사이의 최소 길이
    // maxLow -> 아래껍질 사이의 최대 길이
    // (겹치는 부분의 최대 길이를 구해야 하기 때문에)
    double minUp = 101, maxLow= -1;
    for(int i=0; i<upper.size(); i++){
        if(between(upper[i].first,upper[i].second,x)){
            minUp = min(minUp, at(upper[i].first, upper[i].second,x));
        }
    }
    for(int i=0; i<lower.size(); i++){
        if(between(lower[i].first, lower[i].second, x)){
            maxLow = max(maxLow, at(lower[i].first,lower[i].second,x));
        }
    }
    return minUp-maxLow;

}

double solve(){
    double lo = max(minX(hull1),minX(hull2));
    double hi = min(maxX(hull1),maxX(hull2));
    if(hi<lo) return 0;
    for(int it = 0; it<100; it++){
        double oneThird = (2*lo + hi)/3;
        double twoThird = (lo + 2*hi)/3;
        if(vertical(oneThird) < vertical(twoThird)){
            lo = oneThird;
        }
        else {
            hi = twoThird;
        }
    }
    // 안겹치면 0
    return max(0.0,vertical(hi));
}

int main(){
    int test_case;
    fin >> test_case;
    for(int test=0; test < test_case; test++){
        fin >> n >> m;
        point temp;
        for(int i=0; i< n; i++){
            fin >> temp.x >> temp.y;
            hull1.push_back(temp);
        }
        for(int i=0; i<m; i++){
            fin >> temp.x >> temp.y;
            hull2.push_back(temp);
        }
        decompose(hull1);
        decompose(hull2);
        printf("%0.10f\n",solve());
        Clear();
        //cout << solve() << endl;
    }
}

void Clear(){
    hull1.clear();
    hull2.clear();
    lower.clear();
    upper.clear();
}