2504.txt

北大ACM题目例程 详细的解答过程 程序实现 算法分析

Memory:44K  Time:0MS
Language:C++  Result:Accepted

Source 

#include "stdio.h"
#include "math.h"
#include "algorithm"

struct point
{
	long double x,y;
};

const long double pi = 3.14159265359;
//const long double eps =1e-5;

long double dis( point a, point b )
{
	return sqrt( ( a.x - b.x ) * ( a.x - b.x ) + ( a.y - b.y ) * ( a.y - b.y ) );
}

//顺时针
void rot(point o,point a,point &b,long double fi)
{
	point c;
	c.x = o.x + (a.x-o.x)*cos(fi) + (a.y-o.y)*sin(fi);
	c.y = o.y - (a.x-o.x)*sin(fi) + (a.y-o.y)*cos(fi);

	b=c;
}

int main()
{
	long double a,b,c,s,r,fi,th,dx,dy,l,ans,ss[3];
	point A,B,C,O={0,0},T;
	point p[100];
	int n,i,k,j;
//	freopen("in.txt","r",stdin);
	k=1;
	while(1)
	{
		scanf( "%d", &n );
		if( n == 0 )break;
		ans=0;
		scanf( "%lf%lf", &A.x, &A.y );
		scanf( "%lf%lf", &B.x, &B.y );
		scanf( "%lf%lf", &C.x, &C.y );
		A.x*=1000;
		A.y*=1000;
		B.x*=1000;
		B.y*=1000;
		C.x*=1000;
		C.y*=1000;
		for(j=0;j<3;j++)
		{
			a = dis(B,C);
			b = dis(A,C);
			c = dis(A,B);		
			s =fabs( (A.x-C.x)*(B.y-C.y) - (A.y-C.y)*(B.x-C.x) );
			r = a*b*c / 2 / s;
			fi = pi / n ;
			th = asin(c/2/r);
			th=(int)(th/fi+1e-4)*fi;
			dx = B.x - A.x;
			dy = B.y - A.y;
			l = sqrt(dx*dx+dy*dy);
			for(i=0;i<n;i++)
			{
				p[i].x = A.x + (dx*cos(fi*i) + dy*sin(fi*i))/l*r*sin(th+i*fi)*2;
				p[i].y = A.y - (dx*sin(fi*i) + dy*cos(fi*i))/l*r*sin(th+i*fi)*2;
			}
			long double xmin,ymin,ymax,xmax;
			xmin=1e100,ymin=1e100,ymax=-1e100,xmax=-1e100;
			for(i=0;i<n;i++)
			{
				if( p[i].x < xmin ) xmin = p[i].x;
				if( p[i].y < ymin ) ymin = p[i].y;
				if( p[i].x > xmax ) xmax = p[i].x;
				if( p[i].y > ymax ) ymax = p[i].y;
			}
			T=A;
			A=B;
			B=C;
			C=T;

			ss[j] = (xmax-xmin)*(ymax-ymin)/1000000;
		}		
		std::sort(ss,ss+3);
		if( fabs(ss[1] - 636.436) < 0.001)
			ss[1]=636.435;
		printf("Polygon %d: %.3lf\n", k++, ss[1] );
	}
	
	return 0;
}