pku 1279 art gallery.cpp

来自「Description The art galleries of the ne」· C++ 代码 · 共 129 行

#include <stdio.h>
#include <iostream>
#include <math.h>
#include <algorithm>
using namespace std ;

#define Eps -1e-11
#define MAX 10000
 

struct Line 
{
	double x , y , b; 
};
struct Point
{
	double x , y ; 
};
struct Group
{
	int length ; 
	Point point[MAX] ;
};
Group init , res ;

double Cross(Point a , Point b , Point c)
{
	return (c.x-a.x) * (b.y-a.y) - (c.y-a.y) * (b.x-a.x) ;
}

Line Get_line(Point a , Point b)
{
	Line A ;
	A.x = b.y - a.y ; A.y = -(b.x - a.x) ; A.b = a.y*(b.x-a.x) - a.x*(b.y-a.y);
	return A ;
}

Point Get_insert_point(Point a , Point b , Point c , Point d)
{
	Line A = Get_line(a , b ) ;
	Line B = Get_line(c , d ) ;
	Point ans ;
	ans.y = (A.b*B.x-B.b*A.x) / (A.x*B.y-A.y*B.x);
	if(fabs(A.x) < fabs(Eps))
		ans.x = -(B.y*ans.y+B.b) / B.x ; 
	else
		ans.x = -(A.y*ans.y+A.b) / A.x ; 
	return ans ;
}

bool Equal(Point a , Point b)
{
	if(fabs(a.x-b.x) < 1e-10 && fabs(a.y-b.y) <1e-10)
		return true ;
	return false ;
}

Group run(Point A , Point B)
{
	int i ; Point key ; 
	Group next ; next.length = 0 ;
	for ( i = 0 ; i < res.length - 1; i ++)
	{
		double temp1 , temp2 ;
		temp1 = Cross(A , B , res.point[i]) ; 
		temp2 = Cross(A , B , res.point[i+1]) ;
		if(temp1 > Eps && temp2 > Eps)
		{
			next.point[next.length ++] = res.point[i] ;
			next.point[next.length ++] = res.point[i+1] ;
		}
		else if(temp1 < Eps && temp2 < Eps)
			continue ;
		else
		{
			key = Get_insert_point(A , B , res.point[i] , res.point[i+1]) ;
			if(temp1 > Eps)
			{
				next.point[next.length ++] = res.point[i] ;
				next.point[next.length ++] = key ;
			}
			else
			{
				next.point[next.length ++] = key ; 
				next.point[next.length ++] = res.point[i+1] ;
			}
		}
	}
	if(next.length == 0 )
	{
		res.length = 0 ; 
		return res ;
	}
	res.length = 0 ; 
	res.point[res.length ++] = next.point[0] ; 
	for ( i = 1 ; i < next.length ; i ++)
		if(!Equal(res.point[res.length-1] , next.point[i]))
			res.point[res.length++] = next.point[i] ; 
	if(res.length > 1 && Equal(res.point[0] , res.point[res.length-1]))
		res.length -- ;
	res.point[res.length++] = res.point[0];
	return res ;
}

int main()
{
	int text , Case ;
	while ( 1 == scanf("%d",&text))
	{
		for (Case = 0 ; Case < text ; Case ++)
		{
			int n , i ; 
			scanf("%d",&n);
			for ( i = 0 ; i < n ; i ++)
				scanf("%lf%lf",&init.point[i].x , &init.point[i].y) ;
			init.point[n] = init.point[0] ; 
			init.length = n + 1;
			res = init ;
			for ( i = 0 ; i < init.length - 1 ; i ++)
				res = run(init.point[i] , init.point[i+1] ) ;
			double sum = 0 ; 
			for ( i = 0 ; i < res.length - 1 ; i ++)
				sum += res.point[i].x * res.point[i+1].y - res.point[i].y * res.point[i+1].x ;
			sum = fabs(sum) / 2.0 ; 
			printf("%.2lf\n",sum);
		}
	}
	return 0 ;
}