[BOJ/Platinum 4] 백준 21624 Fence(C++)

문제 링크

https://www.acmicpc.net/problem/21624

 

문제

Donald owns a nice small house in Manhattan. Due to recent elections it is important to protect yourself from the potential public unrest, so Donald has decided to build a fence around his house.

Donald's house can be represented as a polygon on the plane, with all the coordinates being integers. Moreover, all of his house corners are exactly 90deg, and each wall is parallel to either east-west or north-south axis. Donald wants to build a fence so that the house is completely inside of it and that the fence is not too close to the house. More precisely, Donald wants to build a fence in such way that Manhattan distance between any point of the fence and any point of the house is at least l.

Recall that Manhattan distance between points (x1, y1) and (x2, y2) is |x1 − x2| + |y1 − y2|.

Donald wants to minimize building costs, so he asks you to find the smallest possible length of the fence.

 

입력

The first line contains integers n and l (4 ≤ n ≤ 100,000, 0 ≤ l ≤ 10^8).

Each of the next n lines contains integers xi, yi (|xi|, |yi| ≤ 10^8), describing the border of the house in clockwise or counterclockwise order.

It's guaranteed that the house is non-degenerate, doesn't contain any self-intersections (no two segments intersect except the neighboring segments having a common end), no two points coincide, all the house walls are either vertical or horizontal.

 

출력

Print a single real value, the smallest possible length of the fence. Your answer will be considered correct if it's absolute or relative error will be at most 10^−6.

 

예제 입력 1

4 3
-3 -3
-3 3
3 3
3 -3

예제 출력 1

40.9705627485

예제 입력 2

9 0
1 1
3 1
5 1
5 2
3 2
3 3
2 3
2 2
1 2

예제 출력 2

10.6502815399

 

알고리즘 분류

• 그레이엄 스캔

 

풀이

집을 감싸는 울타리의 어느 점과 집의 어느 점이든 전부 최소 L만큼의 거리를 두고 울타리를 쳐야 한다.

이는 맨해튼 거리이며, 울타리의 총 길이가 최소가 되기 위해서는 집의 어떤 점에서 L만큼 떨어져 있는 점들을 기록해야 한다.

하지만, 그렇게 많은 점을 기록할 필요는 없고 동서남북 직선 거리로 L만큼 떨어져 있는 점 4개만 기록하면 된다.

나머지 점들은, 동서남북 직선 거리로 떨어진 점이 울타리에 포함된다면 나머지 점들도 포함될 것이고, 그렇지 않다면 울타리에서 제외될 것이기 때문이다.

아무튼 그렇게 해서 기록되는 점은 총 4N개의 점일 것이고, 이를 그레이엄 스캔을 통해서 볼록 껍질을 구성한다.

볼록 껍질을 구성했으면, 울타리의 길이를 구성한다. 이는 볼록 껍질을 구성하는 점과 점 사이의 거리의 총합이 된다.

 

코드

#include <iostream>
#include <string>
#include <vector>
#include <cmath>
#include <algorithm>
#define LL long long
#define INF 2e9
#define FASTIO cin.tie(0); cout.tie(0); ios::sync_with_stdio(false);

using namespace std;
struct POINT {
	LL X, Y;

	bool operator<(const POINT &A) const {
		if (X != A.X) return (X < A.X);

		return (Y < A.Y);
	}
};

int N;
LL L, X, Y, MinX, MinY, FirstPoint;
LL MoveX[4] = { 0,-1,0,1 };
LL MoveY[4] = { -1,0,1,0 };
vector<POINT> Points, CV;
double Answer;

void init() {
	MinX = INF;
	MinY = INF;
}

LL get_Distance(POINT A, POINT B) {
	return (A.X - B.X) * (A.X - B.X) + (A.Y - B.Y) * (A.Y - B.Y);
}

LL get_CCW(POINT A, POINT B, POINT C) {
	LL OP = (A.X * B.Y) + (B.X * C.Y) + (C.X * A.Y);
	OP -= ((A.Y * B.X) + (B.Y * C.X) + (C.Y * A.X));

	return OP;
}

bool comp(POINT A, POINT B) {
	LL NowCCW = get_CCW(Points[0], A, B);

	if (NowCCW != 0) return (NowCCW > 0);
	if (A.X != B.X) return (A.X < B.X);
	return (A.Y < B.Y);
}

void input() {
	cin >> N >> L;
	for (int i = 0; i < N; i++) {
		cin >> X >> Y;
		for (int j = 0; j < 4; j++) {
			LL NextX = X + (MoveX[j] * L);
			LL NextY = Y + (MoveY[j] * L);
			Points.push_back({ NextX,NextY });
		}
	}
}

void graham_Scan() {
	for (int i = 0; i < (int)Points.size(); i++) {
		if ((MinX > Points[i].X) || ((MinX == Points[i].X) && (MinY > Points[i].Y))) {
			MinX = Points[i].X;
			MinY = Points[i].Y;
			FirstPoint = i;
		}
	}
	swap(Points[0], Points[FirstPoint]);
	sort(Points.begin() + 1, Points.end(), comp);
	for (int i = 0; i < (int)Points.size(); i++) {
		while (((int)CV.size() >= 2) && (get_CCW(Points[i], CV[(int)CV.size() - 2], CV[(int)CV.size() - 1]) <= 0)) {
			CV.pop_back();
		}
		CV.push_back(Points[i]);
	}
	for (int i = 1; i < (int)CV.size(); i++) {
		Answer += sqrt(get_Distance(CV[i - 1], CV[i]));
	}
	Answer += sqrt(get_Distance(CV[(int)CV.size() - 1], CV[0]));
}

void find_Answer() {
	cout << fixed;
	cout.precision(10);
	cout << Answer << "\n";
}

void settings() {
	init();
	graham_Scan();
}

int main() {
	FASTIO
	input();
	settings();
	find_Answer();

	return 0;
}