zoj 1892 || poj 2504 || UVA 10577 Bounding box

这题太坑姐了！！！！

给你正多边形的三个点，求包围它的最小矩形面积（矩形长宽必须平行于x或y）

按理是水题啊，求下三点的外接圆圆心（即正多边形的中心），然后随便找个点旋转向量即可。

有waterloo的测试数据，一直差了点精度，一直在看自己哪点损失精度了，可是旋转向量咋着也得用三角函数吧！！！

最后发现，我选的起始点是y最小的点，如果选输入的第一个点就和人家结果一摸一样了，坑姐啊！！！！神马破题！！

P.S. 测试数据http://plg1.cs.uwaterloo.ca/~acm00/010922/data/ D题

#include <queue>
#include <stack>
#include <math.h>
#include <stdio.h>
#include <stdlib.h>
#include <iostream>
#include <limits.h>
#include <string.h>
#include <string>
#include <algorithm>

using namespace std;

struct point{double x,y;};
const double inf = 1e20;
const double pi = acos(-1.0);
point p[3];
const double eps = 1e-10; 
bool dy(double x,double y)	{	return x > y + eps;}	// x > y 
bool xy(double x,double y)	{	return x < y - eps;}	// x < y 
bool dyd(double x,double y)	{ 	return x > y - eps;}	// x >= y 
bool xyd(double x,double y)	{	return x < y + eps;} 	// x <= y 
bool dd(double x,double y) 	{	return fabs( x - y ) < eps;}  // x == y
point l2l_inst_p(point u1,point u2,point v1,point v2)
{
	point ans = u1;
	double t = ((u1.x - v1.x)*(v1.y - v2.y) - (u1.y - v1.y)*(v1.x - v2.x))/
				((u1.x - u2.x)*(v1.y - v2.y) - (u1.y - u2.y)*(v1.x - v2.x));
	ans.x += (u2.x - u1.x)*t;
	ans.y += (u2.y - u1.y)*t;
	return ans;
}
point circumcenter(point a,point b,point c)
{
	point ua,ub,va,vb;
	ua.x = ( a.x + b.x )/2;
	ua.y = ( a.y + b.y )/2;
	ub.x = ua.x - a.y + b.y;//根据 垂直判断，两线段点积为0 
	ub.y = ua.y + a.x - b.x;
	va.x = ( a.x + c.x )/2;
	va.y = ( a.y + c.y )/2;
	vb.x = va.x - a.y + c.y;
	vb.y = va.y + a.x - c.x;
	return l2l_inst_p(ua,vb);
} 
point Whirl(double cosl,double sinl,point a,point b)
{    
       b.x -= a.x; b.y -= a.y;
       point c;
       c.x = b.x * cosl - b.y * sinl + a.x;
       c.y = b.x * sinl + b.y * cosl + a.y;
       return c;
}
 
int main()
{
	int n,ind = 1;
	double minx,miny,maxx,maxy;
	while( ~scanf("%d",&n) && n )
	{
		minx = miny = inf; maxx = maxy = -inf;
		for(int i=0; i<3; i++)
			scanf("%lf%lf",&p[i].x,&p[i].y);
		
		point c = circumcenter(p[0],p[1],p[2]);
		point s = p[0],k;
		double a = 2*pi/n;
		for(int i=0; i<n; i++)
		{
			k = Whirl(cos(i*a),sin(i*a),c,s);
			if( xy(k.x,minx) ) minx = k.x;
			if( xy(k.y,miny) ) miny = k.y;
			if( dy(k.x,maxx) ) maxx = k.x;
			if( dy(k.y,maxy) ) maxy = k.y;	
		}
		
		double ans = (maxx - minx)*(maxy - miny);
		printf("Polygon %d: %.3lfn",ind++,ans);
	}

return 0;
}

（编辑：李大同）

【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容!