[BOJ] tag: minimum enclosing circle

엄청 오랜만에 글을 올리게 되었다.

여러 프로젝트, 업무, 공부를 하다보니 글을 쓰는 걸 되게 뒤로 미루었던 것 같다.

 

일단, 이번에는 최소 외접원 문제에 대해서 다루어 보려한다.

 

먼저 관련 문제 목록부터 보겠다.

www.acmicpc.net/problem/13708

13708번: 모든 점을 포함하는 원

www.acmicpc.net/problem/2389

2389번: 세상의 중심에서...

www.acmicpc.net/problem/11930

11930번: Smallest Enclosing Sphere

www.acmicpc.net/problem/2626

2626번: 헬기착륙장

 

대충 문제들을 보면 어떤 유형의 문제인지 알 수 있을 듯 하다.

 

사실 이 문제의 아이디어는 algo_know_yeah 팀원인 antifly55에게 배웠는데, 굉장히 내 머리를 때리는 방법이었다.

바로 이전 학기에 수치해석 강의에서 배운 방법이었는데, 바로 경사하강법의 아이디어이다.

 

생각해보면 정말 쉽다.

1. 일단 가상의 점을 하나 잡는다.(이 점이 점차 원의 중심에 가까워진다고 생각하면 된다.)

2. 가상의 점이 일단 최대한 근접해서 시작하면 좋으니 점들의 평균에서 시작하자.

3. 현재 잡은 가상의 점에서 주어진 점 중 가장 먼 점으로 살짝식 다가가자. 그리고 점차 다가가는 정도를 줄여나가자.

 

이렇게 하다보면 어느순간 해에 다가갈 것이다. 정말 신기하게도 ㅇ.ㅇ...

 

일단 13708번 문제의 코드를 첨부하도록 하겠다..

정말 알아두면 쓸만한 아이디어이니 직접 한번 공부해보는 걸 추천드린다.!

 

#include <bits/stdc++.h>

#define for1(s,n) for(int i = s; i < n; i++)
#define for1j(s,n) for(int j = s; j < n; j++)
#define foreach(k) for(auto i : k)
#define foreachj(k) for(auto j : k)
#define pb(a) push_back(a)
#define sz(a) a.size()

using namespace std;
typedef unsigned long long ull;
typedef long long ll;
typedef vector <int> iv1;
typedef vector <vector<int>> iv2;
typedef vector <ll> llv1;
typedef unsigned int uint;
typedef vector <ull> ullv1;
typedef vector <vector <ull>> ullv2;

struct Point {
    double x, y;
    Point() : x(0), y(0) {}
    Point(double x, double y) : x(x), y(y) {}
};

Point getAveragePoint(Point* array, ll len) {
    Point ret = Point(0, 0);
    for1(0, len) {
        ret.x += array[i].x;
        ret.y += array[i].y;
    }
    ret.x/=len;
    ret.y/=len;
    return ret;
}

double getDistance(Point a, Point b) {
    return (a.x - b.x)*(a.x - b.x) + (a.y - b.y)*(a.y - b.y);
}

Point getFarestPoint(Point* array, ll len, Point crt) {
    Point ret = Point(crt.x, crt.y);
    for1(0, len) {
        if(getDistance(array[i], crt) > getDistance(ret, crt)) {
            ret = Point(array[i].x , array[i].y);
        }
    }
    return ret;
}

ll N;
Point ar[330];
ll gen = 100000;
double learning_rate = 1;

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

    cin >> N;
    for1(0, N) {
        cin >> ar[i].x >> ar[i].y;
    }   

    Point current = getAveragePoint(ar, N);

    for1(0, gen) {
        Point farPoint = getFarestPoint(ar, N, current);
        current.x = current.x + (farPoint.x - current.x) * learning_rate;
        current.y = current.y + (farPoint.y - current.y) * learning_rate;
        learning_rate *= 0.999;
    }

    Point farPoint = getFarestPoint(ar, N, current);
    cout << fixed;
    cout.precision(2);
    cout << sqrt(getDistance(current, farPoint))*2;
}