1010 area.cpp

ACM比赛解题报告,包括hdu1880、zoj1010、zoj1015

#include<iostream>
using namespace std;

struct Point
{
	double x, y;
};

Point pList[ 1005 ];
int N;

double direction( Point p1, Point p2, Point p3 );
bool onSegment( Point x, Point y, Point p );
bool different( double a, double b );
bool intersect( Point x1, Point y1, Point x2, Point y2 );

void read()
{
	int i;
	for ( i = 0; i < N; i ++ )
		cin >> pList[ i ].x >> pList[ i ].y;
}

bool check()
{
	if ( N < 3 )
		return false;

	int i, j;
	for ( i = 0; i < N; i ++ )
		for ( j = i + 2; j < N; j ++ )
		{
			int x = ( i + 1 ) % N;
			int y = ( j + 1 ) % N;
		 
			if ( !( i == 0 && y == 0 ) && intersect( pList[ i ], pList[ x ], pList[ j ], pList[ y ] ) )
				return false;
		 
		}

	return true;
}

double area()
{
	double res = 0.0;
	for ( int i = 1; i < N - 1; i ++ )
		res += direction( pList[ 0 ], pList[ i ], pList[ i + 1 ] );

	res = res / 2;
	if ( res < 0 )
		return -res;
	else
		return res;
}

int main()
{
	int i = 0;
	while ( scanf( "%d", &N ) != EOF && N )
	{	
		read();

		if ( i )
			putchar( '\n' );
		if ( check() )
			printf( "Figure %d: %.2f\n", ++ i, area() );
		else
			printf( "Figure %d: Impossible\n", ++ i );
	}

	return 0;
}

double direction( Point p1, Point p2, Point p3 )
{
	double x1 = p2.x - p1.x;
	double y1 = p2.y - p1.y;
	double x2 = p3.x - p1.x;
	double y2 = p3.y - p1.y;

	return x1 * y2 - x2 * y1;
}

bool onSegment( Point x, Point y, Point p )
{
	return p.x >= x.x && p.x <= y.x && p.y >= x.y && p.y <= y.y;
}

bool different( double a, double b )
{
	return a > 0 && b < 0 || a < 0 && b > 0;
}

bool intersect( Point x1, Point y1, Point x2, Point y2 )
{
	double d1 = direction( x2, y2, x1 );
	double d2 = direction( x2, y2, y1 );
	double d3 = direction( x1, y1, x2 );
	double d4 = direction( x1, y1, y2 );

	if ( different( d1, d2 ) && different( d3, d4 ) )
		return true;

	if ( d1 == 0 && onSegment( x2, y2, x1 ) ||
		 d2 == 0 && onSegment( x2, y2, y1 ) ||
		 d3 == 0 && onSegment( x1, y1, x2 ) ||
		 d4 == 0 && onSegment( x1, y1, y2 ) )
		 return true;

	return false;
}