[UVa] 10112 - Myacm Triangles

題目網址: http://goo.gl/7ZyxtQ

題 意: 給 n 個點(4 <= n <= 15)，求面積最大的三角形，且三角形內不包含其它點。


解法: 枚舉所有情況 O(n^3)，且檢查其它點的包含情況 O(n)，再記錄最大面積的三角形。

TAG: Computational Geometry

注意:

程式碼:

	/**
	* Tittle: 10112 - Myacm Triangles
	* Author: Cheng-Shih, Wong
	* Date: 2015/03/30
	*/
	// include files
	#include <iostream>
	#include <cstdio>
	#include <cstring>
	#include <cmath>
	using namespace std;
	// definitions
	#define FOR(i,a,b) for( int i=(a),_n=(b); i<=_n; ++i )
	#define clr(x,v) memset( x, v, sizeof(x) )
	#define EPS 1e-6
	#define N 20
	class Point {
	public:
	double x, y;
	Point( double _x=0, double _y=0 ): x(_x), y(_y) {}
	const Point operator-( const Point &op ) const {
	return Point(x-op.x,y-op.y);
	}
	const double operator^( const Point &op ) const {
	return x*op.y-y*op.x;
	}
	};
	// declarations
	int n;
	Point p[N];
	// functions
	const double triArea( const Point &a, const Point &b, const Point &c )
	{
	return 0.5*abs( (b-a)^(c-a) );
	}
	const int dcmp( const double &x )
	{
	if( x < -EPS ) return -1;
	return x > EPS;
	}
	const bool judge( int A, int B, int C, double &area )
	{
	static double ta;
	Point &a = p[A];
	Point &b = p[B];
	Point &c = p[C];
	area = triArea( a, b, c );
	FOR( i, 1, n ) {
	if( i==A || i==B || i==C ) continue;
	ta = triArea(a,b,p[i])+triArea(b,c,p[i])+triArea(c,a,p[i]);
	if( dcmp(ta-area) == 0 )
	return false;
	}
	return true;
	}
	// main function
	int main( void )
	{
	char name[10];
	double maxA, tmp;
	int mi, mj, mk;
	// input
	while( scanf( "%d", &n )==1 && n ) {
	FOR( i, 1, n )
	scanf( "%s%lf%lf", name, &p[i].x, &p[i].y );
	// solve
	maxA = 0;
	FOR( i, 1, n ) FOR( j, i+1, n ) FOR( k, j+1, n ) {
	if( judge(i,j,k,tmp) && dcmp(maxA-tmp)<0 ) {
	maxA = tmp;
	mi = i;
	mj = j;
	mk = k;
	}
	}
	// output
	printf( "%c%c%c\n", mi+'A'-1, mj+'A'-1, mk+'A'-1 );
	}
	return 0;
	}

view raw 10112 - Myacm Triangles.cpp hosted with ❤ by GitHub