취미로 코딩하기

※ 글쓴이는 취미로 코딩을 익혀보는 사람이라 정확하지 않은 내용을 담고 있을 수 있다 ※

이번에 볼 문제는 백준 6646번 문제인 Wooden Fence이다.
문제는 아래 링크를 확인하자.

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

벨 나무들을 먼저 결정한다면, 남은 나무를 감싸는 울타리의 최소 길이는 남은 나무들로 이루어진 Convex Hull의 둘레의 길이와 같음을 관찰하자.

이 둘레의 길이가 베어진 나무로 만들 수 있는 울타리의 길이보다 작거나 같은 모든 경우를 찾아 각 경우의 베어진 나무의 가치의 합을 계산하고, 그 중 최솟값을 찾아 문제를 해결하자. 전체 나무 수\(N\)의 값이 16 이하로 매우 작으므로 모든 경우를 조사해도 충분히 문제를 해결할 수 있다.

아래는 제출한 소스코드이다.

#include <iostream>
#include <vector>
#include <algorithm>
#include <cmath>
using namespace std;
typedef long double ld;

struct point {
	int x, y, v, l;
	point() {};
	bool operator< (point &p) {
		if (x != p.x) return x < p.x;
		return y < p.y;
	}
};

int CCW(point &p1, point &p2, point &p3) {
	return p1.x * p2.y + p2.x * p3.y + p3.x * p1.y - p1.x * p3.y - p2.x * p1.y - p3.x * p2.y;
}

int N, NN;
point P[16];
int ans = 1000000007;
vector<point> uhull, lhull;

void buildhull(int cN) {
	uhull.clear();
	for (int i = 0, b = 1; i < N; i++, b <<= 1) {
		if (cN & b) continue;
		while (uhull.size() > 1) {
			if (CCW(uhull[uhull.size() - 2], uhull.back(), P[i]) < 0) break;
			uhull.pop_back();
		}
		uhull.emplace_back(P[i]);
	}
	lhull.clear();
	for (int i = 0, b = 1; i < N; i++, b <<= 1) {
		if (cN & b) continue;
		while (lhull.size() > 1) {
			if (CCW(lhull[lhull.size() - 2], lhull.back(), P[i]) > 0) break;
			lhull.pop_back();
		}
		lhull.emplace_back(P[i]);
	}

	ld d = 0; int v = 0, l = 0, usize = uhull.size(), lsize = lhull.size();
	for (int i = 0; i + 1 < usize; i++) {
		d += hypotl(abs(uhull[i + 1].x - uhull[i].x), abs(uhull[i + 1].y - uhull[i].y));
	}
	for (int i = 0; i + 1 < lsize; i++) {
		d += hypotl(abs(lhull[i + 1].x - lhull[i].x), abs(lhull[i + 1].y - lhull[i].y));
	}
	for (int i = 0, b = 1; i < N; i++, b <<= 1) {
		if (!(cN & b)) continue;
		v += P[i].v, l += P[i].l;
	}
	if (d > l) return;
	ans = min(ans, v);
}

void solve() {
	NN = 1 << N;
	for (int i = 0; i < N; i++) cin >> P[i].x >> P[i].y >> P[i].v >> P[i].l;
	sort(P, P + N);
	ans = 1000000007;
	for (int i = 0; i + 1 < NN; i++) buildhull(i);
	cout << "The lost value is " << ans << ".\n";
}

int T;

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

	cin >> N;
	while (N) {
		solve();
		cin >> N;
	}
}