BOJ 7684 Convex Area

문제 링크입니다.

문제 요약

3차원 공간 상에 주어진 $N \le 25$개 점의 볼록 껍질의 겉넓이를 구하세요. 볼록 껍질 위의 서로 다른 네 점은 한 평면 위에 있지 않습니다.

풀이

볼록 껍질의 한 가지 특징은 경계면을 기점으로 나머지 모든 점이 한쪽 공간에만 위치한다는 점입니다. 이를 이용합시다.

임의로 세 점을 잡아 후보 평면을 고정할 수 있습니다. ${\cal O} (N^3)$가지 후보가 존재하겠죠. 각 후보 평면을 경계면으로 했을 때 나머지 모든 점이 한쪽에 있는지 판별하면 됩니다.

평면을 기점으로 전이 어느 쪽에 위치해 있는지는 해당 평면의 법선벡터와의 내적의 부호로 확인할 수 있습니다. 평면을 고정하는 때 이용되지 않은 $N-3$개의 점 모두에 대해 이를 확인해 주면 총 시간 복잡도 ${\cal O}(N^4)$에 문제를 해결할 수 있습니다.

코드

#include<bits/stdc++.h>
using namespace std;
using ll = long long;
using pii = pair<int, int>;
using pll = pair<ll, ll>;
using ld = long double;
using p = array<ll, 3>;

p operator+(p a, p b){
	return {a[0]+b[0], a[1]+b[1], a[2]+b[2]};
}
p operator-(p a, p b){
	return {a[0]-b[0], a[1]-b[1], a[2]-b[2]};
}
ll dot(p a, p b){
	return a[0]*b[0]+a[1]*b[1]+a[2]*b[2];
}
p cross(p a, p b){
	return {a[1]*b[2]-a[2]*b[1], a[2]*b[0]-a[0]*b[2], a[0]*b[1]-a[1]*b[0]};
}
ld getSize(p a){
	return sqrtl(ld(a[0]*a[0]+a[1]*a[1]+a[2]*a[2]));
}
ld getArea(p a, p b, p c){
	return getSize(cross(b-a, c-a))/2;
}

int main(){
	cin.tie(0);cout.tie(0);ios::sync_with_stdio(false);
	int n; while(cin >> n){
		if(!n) return 0; ld ans = 0;
		vector<p> a(n); for(int i = 0; i < n; i++) cin >> a[i][0] >> a[i][1] >> a[i][2];
		for(int i = 0; i < n; i++) for(int j = 0; j < i; j++) for(int k = 0; k < j; k++){
			p orth = cross(a[j]-a[i], a[k]-a[i]);
			bool noplus = 0, nominus = 0;
			for(int q = 0; q < n; q++) if((q-i)*(q-j)*(q-k)){
				ll dir = dot(a[q]-a[i], orth);
				if(dir >= 0) nominus = 1;
				if(dir <= 0) noplus = 1;
			}
			if(!noplus || !nominus) ans += getArea(a[i], a[j], a[k]);
		}
		cout << round(ans) << '\n';
	}
}