BOJ 10903 - Wall construction

문제 태그 : https://www.acmicpc.net/problem/10903

문제 소개

원의 갯수와, 원의 반지름과 각 원의 중심의 위치가 주어진다. (모든 원은 반지름이 같다.) 이때 모든 원을 포함하는 도형의 최소 둘레를 구하시오.

문제 풀이

이 문제를 보자마다 딱 이러한 형태의 그림이 떠올랐다.

그림을 보면 알겠지만, 바깥의 전체 둘레의 길이는 원하나의 둘레+ 점 들 사이의 거리의 합이다. 이 그림을 고려하며 문제를 다시 보면, 볼록껍질을 이루는 점들의 이웃한 거리의 합 + 원 하나의 둘레가 정답이 된다는 것을 알 수 있다.
볼록껍질을 잡는 것은 이 글을 통해서 배울 수 있다.

코드

#include<bits/stdc++.h>
using namespace std;
typedef long long int ll;
 
struct poi{
    ll x,y;
};
 
ll ccw(poi a,poi m,poi b)
{
    ll t=(a.x-m.x)*(b.y-m.y)-(a.y-m.y)*(b.x-m.x);
    return (t<0)-(t>0);
}
 
ll cccw(poi a,poi b,poi c,poi d){
    d.x-=(c.x-b.x);
    d.y-=(c.y-b.y);
    return ccw(a,b,d);
}
 
ll dist(poi a,poi b)
{
    return (b.x-a.x)*(b.x-a.x)+(b.y-a.y)*(b.y-a.y);
}
 
poi arr[1010101];
 
bool sf(poi a,poi b){
    if(a.x!=b.x)return a.x<b.x;
    return a.y<b.y;
}
 
bool sf2(poi a,poi b){
    return (ccw(arr[1],a,b)>0||(ccw(arr[1],a,b)==0&&dist(arr[1],a)<dist(arr[1],b)));
}
 
poi ch[1010101];
 
int main(){
    ll i,j,k,l,m,n;
    scanf("%lld %lld",&n,&m);
    for(i=1;i<=n;i++)
        scanf("%lld %lld",&arr[i].x,&arr[i].y);
    sort(arr+1,arr+1+n,sf);
    sort(arr+2,arr+1+n,sf2);
    long double ans=6.283185307180*(long double)m;
    if(n==1){
        cout << fixed;
        cout.precision(12);
        cout<<ans;
        return 0;
    }
    ch[0]=arr[1];
    ch[1]=arr[2];
    ll fl=2;
    for(i=3;i<=n;i++){
        while(fl>=2&&ccw(ch[fl-2],ch[fl-1],arr[i])<=0)
            fl--;
        ch[fl]=arr[i];
        fl++;
    }
    ch[fl]=ch[0];
    for(i=1;i<=fl;i++){
        ans+=(long double)sqrt(dist(ch[i],ch[i-1]));
    }
    cout << fixed;
    cout.precision(12);
    cout<<ans;
}