HDOJ 1348 벽 (볼록 가방)

[제목] n 개의 점 을 주 었 습 니 다. 이 n 개의 돌출 된 가방 의 가장자리 길이 와 주어진 원 의 둘레 를 더 해 주세요!
[분석] 첫 번 째 로 볼록 가방 문 제 를 풀 었 는데 이 문 제 를 통 해 볼록 가방 이 무엇 인지 알 게 되 었 습 니 다. 신기 합 니 다. 여기 서 볼록 가방 을 구 하 는 방법 을 공유 하 는 블 로그 입 니 다. 개인 적 으로 잘 썼 다 고 생각 합 니 다. 클릭 하여 링크 를 엽 니 다! ~ ~ ~
[문제 풀이 사고] 돌출 템 플 릿 으로 최소 돌출 백 을 구하 면 됩 니 다. 여기 서 가장 자주 사용 하 는 것 은 위 블 로그 에서 언급 한 Andrew 알고리즘 일 수 있 습 니 다. (여 기 는 수평 순서 입 니 다) 먼저 = x = 작은 것 부터 큰 것 까지 정렬 (x 가 같 으 면 y 로 정렬) 하고 중복 점 을 삭제 한 후에 서열 p1, p2,... 그리고 p1, p2 를 돌출 백 에 넣 고 p3 부터 새로운 점 이 돌출 백 에서 '전진' 할 때방향의 왼쪽 에 있 을 때 계속 하 세 요. 그렇지 않 으 면 최근 에 돌출 된 점 을 삭제 하고 새로운 점 이 왼쪽 에 있 을 때 까지 순서대로 삭제 합 니 다.
[복잡 도] 분석 하면 이 알고리즘 은 정렬 한 후에 왼쪽 에서 오른쪽으로, 오른쪽 에서 왼쪽으로 한 번 씩 스 캔 했 을 뿐 시간 복잡 도 는 O (n) 입 니 다. 게다가 정렬 하 는 시간 복잡 도 는 O (n * logn) 입 니 다!
[ps] 그 러 고 보 니 이것 은 경사 율 최적화 와 밀접 하 게 결합 되 었 습 니 다. 그곳 에서 유지 하 는 돌출 은 바로 돌출 된 가방 이 아 닙 니까?
[AC 코드]

#include <set>
#include <map>
#include <math.h>
#include <vector>
#include <stdio.h>
#include <iostream>
#include <algorithm>
using namespace std;
const int maxn = 10010;
const double PI = acos(-1);
struct Point{
    int x,y;
    Point(){}
    Point(int x,int y):x(x),y(y){}
    bool operator<(const Point &rhs)const{
        if(x==rhs.x) return y<rhs.y;
        return x<rhs.x;
    }
}q[maxn],p[maxn];
int Cross(const Point &a,const Point &b){
    return a.x*b.y-a.y*b.x;
}
double get_Dis(const Point &a,const Point &b){
    return (double)sqrt((a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y));
}
int main(){
    int T,n,r;
    scanf("%d",&T);
    while(T--){
        scanf("%d%d",&n,&r);
        for(int i=0; i<n; i++) scanf("%d%d",&q[i].x,&q[i].y);
        sort(q,q+n);
        int m = 0;
        for(int i=0; i<n; i++){//"   "
            while(m>1&&Cross(Point(p[m-1].x-p[m-2].x,p[m-1].y-p[m-2].y),Point(q[i].x-p[m-2].x,q[i].y-p[m-2].y))<=0) m--;
            p[m++] = q[i];
        }
        int k = m;
        for(int i=n-2; i>=0; i--){//"   "
            while(m>k&&Cross(Point(p[m-1].x-p[m-2].x,p[m-1].y-p[m-2].y),Point(q[i].x-p[m-2].x,q[i].y-p[m-2].y))<=0) m--;
            p[m++] = q[i];
        }
        if(n>1) m--;
        double sum = 0;
        for(int i=0,j=1; i<m; i++,j++){
            sum += get_Dis(p[i],p[j]);
        }
        sum += 2*PI*r;
        printf("%.0f
",sum);
        if(T) puts("");
    }
    return 0;
}