[COGS&USACO]896.젖소 우리(볼록 가방)

http://cojs.tk/cogs/problem/problem.php?pid=896
나의 계산 기하학 입문 문제...
백서 의 계산 기하학 적 부분 을 보 았 는데,그래.
너희들 은 모두 벡터 를 사용한다!!!!
왜 굳이 두 개의 점 을 하나의 선 으로 정 하고 원점 o 에서 출발 하 는 방사선 으로!!!!
이게 소위 노 는 콘 셉 트 인가요?
그리고 이른바 벡터 가감 은 이런 벡터 기점 이 같 아서 원점 o 에서 출발 하 는 방사선 이 된다!!!
그리고 콘 셉 트 도 하고 있어!무릎 꿇 었 어.
(이상 은 순 전 히 33951 입 니 다.
좋아,기 하 를 계산 하 는 것 은 매우 유용 해.많은 조작 을 간소화 하 였 다.
여기에 또 어떤 점 이 쌓 이 고 어떤 것 이 쌓 여 있다.점 적 은 같은 출발점 의 벡터(종점)의 x 좌표 곱 하기+y 좌표 곱 하기 이다.
푸.멋있다!!
계산 이 얼마나 신기 한 지!!
많은 조작 을 간소화 했다!!!
나 는 내 가 그 를 사랑 하 게 되 었 다 는 것 을 발견 했다!!
 
(토로 완료)
이 문제 로...벌 거 벗 은 볼록 가방.
백서 에 있 습 니 다.저 는 말 하지 않 겠 습 니 다.바로 쓸 어 가서 포크 의 양 과 부 를 판단 하 는 것 입 니 다.즉,벡터 왼쪽 에 있 는 지 오른쪽 에 있 는 지 왼쪽 에 있 는 지 계속 하고 오른쪽 에 있 으 면 스 택 에서 다시 하 는 것 입 니 다.

#include <cstdio>

#include <cstring>

#include <cmath>

#include <string>

#include <iostream>

#include <algorithm>

#include <string>

using namespace std;

#define rep(i, n) for(int i=0; i<(n); ++i)

#define for1(i,a,n) for(int i=(a);i<=(n);++i)

#define for2(i,a,n) for(int i=(a);i<(n);++i)

#define for3(i,a,n) for(int i=(a);i>=(n);--i)

#define for4(i,a,n) for(int i=(a);i>(n);--i)

#define CC(i,a) memset(i,a,sizeof(i))

#define read(a) a=getint()

#define print(a) printf("%d", a)

#define dbg(x) cout << #x << " = " << x << endl

#define printarr(a, n, m) rep(aaa, n) { rep(bbb, m) cout << a[aaa][bbb]; cout << endl; }

inline const int getint() { int r=0, k=1; char c=getchar(); for(; c<'0'||c>'9'; c=getchar()) if(c=='-') k=-1; for(; c>='0'&&c<='9'; c=getchar()) r=r*10+c-'0'; return k*r; }

inline const int max(const int &a, const int &b) { return a>b?a:b; }

inline const int min(const int &a, const int &b) { return a<b?a:b; }



using namespace std;



void setio(string name){

	string in = name + ".in", out = name + ".out";

	ios::sync_with_stdio(false);

	freopen(in.c_str(), "r", stdin);

	freopen(out.c_str(), "w", stdout);

}



const int N=10005;

struct node { 

	double x, y; 

	node(const double &_x=0, const double &_y=0) : x(_x), y(_y) {}

}st[N], p[N];

int cnt, n;

node operator - (const node &a, const node &b) { return node(a.x-b.x, a.y-b.y); }

double cross(const node &a, const node &b) { return a.x*b.y-b.x*a.y; }

const bool cmp(const node &a, const node &b) { return (a.x==b.x)?(a.y<b.y):(a.x<b.x); }

const double dis(const node &a, const node &b) { return sqrt((a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y)); }

void tubao() {

	sort(p, p+n, cmp);

	cnt=0;

	rep(i, n) {

		while(cnt>1 && cross(st[cnt-1]-st[cnt-2], p[i]-st[cnt-2])<=0) --cnt;

		st[cnt++]=p[i];

	}

	int k=cnt;

	for3(i, n-2, 0) {

		while(cnt>k && cross(st[cnt-1]-st[cnt-2], p[i]-st[cnt-2])<=0) --cnt;

		st[cnt++]=p[i];

	}

	if(n>1) --cnt;

}



int main() {

	setio("fc");

	scanf("%d", &n);

	rep(i, n) scanf("%lf%lf", &p[i].x, &p[i].y);

	tubao();

	double ans=0;

	for1(i, 0, cnt-1) ans+=dis(st[i], st[i+1]);

	printf("%.2lf
", ans);

	return 0;

}

 
 
 
 
 
묘사 하 다.
농부 존 은 젖 소 를 둘러싸 기 위해 울 타 리 를 만 들 려 고 했 지만 자금 이 부족 했다.그 가 만 든 울 타 리 는 젖소 가 풀 을 좋아 하 는 모든 곳 을 포함해 야 한다.제 시 된 이 지점 의 좌 표 는 이 점 들 을 둘 러 쌀 수 있 는 가장 짧 은 울타리 의 길 이 를 계산한다.
PROGRAM NAME: fc
INPUT FORMAT(file fc.in)
입력 한 데이터 의 첫 줄 에는 정수 N 이 포함 되 어 있 습 니 다.N(0<=N<=10,000)은 농부 존 이 둘러싸 고 싶 어 하 는 방목 점 의 수 를 나타 낸다.다음 N 행,각 줄 은 두 개의 실수 로 구성 되 어 있 으 며,Xi 와 Yi 는 평면 상의 방목 점 좌표(-1,000,000<=Xi,Yi<=1,000,000)에 대응 합 니 다.숫자 는 소수 로 표시 한다.
OUTPUT FORMAT(file fc.out)
출력 은 반드시 하나의 실 수 를 포함 하여 필요 한 울타리 의 길 이 를 표시 해 야 한다.답 은 두 개의 소 수 를 보류한다.
SAMPLE INPUT (file fc.in)

4

4 8

4 12

5 9.3

7 8 

SAMPLE OUTPUT (file fc.out)

12.00