2152.cpp

哈尔滨工业大学ACM 竞赛网上在线试题集锦的源代码

/*  This Code is Submitted by wywcgs for Problem 2152 on 2006-08-18 at 15:52:55 */ 
#include <cstdio>
#include <cmath>
#include <algorithm>
using namespace std;

typedef long long int64;
const int N = 32;

class Point  {
public:
	int c[3];
	void make() { scanf("%d %d %d", &c[0], &c[1], &c[2]); }
};

Point p[N];
int m[4][3];

int det(int, int, int);
int pos(const Point&);
double area(const Point&, const Point&, const Point&);
double dis(int64 x, int64 y, int64 z) { return sqrt(1.0*x*x+y*y+z*z); }

int main()
{
	int n;
	
	while(scanf("%d", &n) != EOF && n != 0) {
		for(int i = 0; i < n; i++) p[i].make();
		double A = 0;
		for(int i = 0; i < n; i++) {
			for(int j = 0; j < 3; j++) m[0][j] = p[i].c[j];
			for(int j = i+1; j < n; j++) {
				for(int k = 0; k < 3; k++ ) m[1][k] = p[j].c[k];
				for(int k = j+1; k < n; k++) {
					for(int l = 0; l < 3; l++) m[2][l] = p[k].c[l];
					bool u = false, d = false;
					for(int l = 0; l < n; l++) {
						if(l == i || l == j || l == k) continue;
						if(pos(p[l]) < 0) u = true;
						else d = true;
					}
					if(!u || !d) A += area(p[i], p[j], p[k]);
				}
			}
		}
		printf("%.0lf\n", A);
	}
	
	return 0;
}

int det(int i, int j, int k)
{
	return m[i][0]*m[j][1]*m[k][2]+m[j][0]*m[k][1]*m[i][2]+m[k][0]*m[i][1]*m[j][2]
			-m[i][2]*m[j][1]*m[k][0]-m[j][2]*m[k][1]*m[i][0]-m[k][2]*m[i][1]*m[j][0];
}
int pos(const Point& a)
{
	for(int i = 0; i < 3; i++) m[3][i] = a.c[i];
	return det(1, 2, 3)-det(0, 2, 3)+det(0, 1, 3)-det(0, 1, 2);
}
double area(const Point& a, const Point& b, const Point& c)
{
	int64 x1 = a.c[0]-b.c[0], y1 = a.c[1]-b.c[1], z1 = a.c[2]-b.c[2];
	int64 x2 = a.c[0]-c.c[0], y2 = a.c[1]-c.c[1], z2 = a.c[2]-c.c[2];
	return dis(x1*y2-x2*y1, x1*z2-x2*z1, y1*z2-y2*z1)/2;
}