[UVa] 10078 - The Art Gallery

題目網址: http://goo.gl/krxXTk

題 意: 給一多邊形，如果在多邊形內部存在一個點無法看見所有的多邊形角，則稱此點為 "critical point"，問多邊形是否存在 "critical point"。


解法: 其實就是問給定多邊形是否為 "凸多邊形"，凸多邊形的檢測方法是檢查所有兩兩相鄰的邊外積是否同向，如果知道外積的含意應該很好懂。

TAG: Computational Geometry,

注意:

程式碼:

	/**
	* Tittle: 10078 - The Art Gallery
	* Author: Cheng-Shih, Wong
	* Date: 2015/03/17
	* File: 10078 - The Art Gallery.cpp - solve it
	*/
	// include files
	#include <iostream>
	#include <cstdio>
	#include <cstring>
	#include <vector>
	#include <algorithm>
	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-8
	inline const double sqr( const double &x );
	const int dcmp( const double &x );
	struct Point {
	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 Point operator-( const Point &op ) const { return Point( x-op.x, y-op.y ); }
	const Point operator*( const double &k ) const { return Point( x*k, y*k ); }
	const Point operator/( const double &k ) const { double t=(dcmp(k)?k:1); return Point( x/t, y/t ); }
	const double operator*( const Point &op ) const { return ( x*op.x + y*op.y ); }
	const double operator^( const Point &op ) const { return ( x*op.y - y*op.x ); }
	const bool operator==( const Point &op ) const { return ( !dcmp(x-op.x)&&!dcmp(y-op.y) ); }
	const bool operator!=( const Point &op ) const { return ( dcmp(x-op.x)||dcmp(y-op.y) ); }
	};
	typedef vector<Point> Polygon;
	// declarations
	int n;
	Polygon p;
	// functions
	const int dcmp( const double &x )
	{
	if( x < -EPS ) return -1; return x > EPS;
	}
	/* return the square of x */
	inline const double sqr( const double &x ) { return x*x; }
	const bool check( const Polygon &P )
	{
	static int dir;
	dir = dcmp( (P[1]-P[0])^(P[2]-P[1]) );
	FOR( i, 0, n-1 ) {
	const Point &a = P[i];
	const Point &b = P[(i+1)%n];
	const Point &c = P[(i+2)%n];
	if( dcmp((b-a)^(c-b)) != dir ) return true;
	}
	return false;
	}
	// main function
	int main( void )
	{
	double x, y;
	// input
	while( scanf( "%d", &n )==1 && n ) {
	p.clear();
	FOR( i, 1, n ) {
	scanf( "%lf%lf", &x, &y );
	p.push_back( Point(x,y) );
	}
	// solve & output
	if( check(p) ) puts("Yes");
	else puts("No");
	}
	return 0;
	}

view raw 10078 - The Art Gallery.cpp hosted with ❤ by GitHub