2013
11-11

# Bounding box

The Archeologists of the Current Millenium (ACM) now and then discover ancient artifacts located at vertices of regular polygons. The moving sand dunes of the desert render the excavations difficult and thus once three vertices of a polygon are discovered there is a need to cover the entire polygon with protective fabric.

Input contains multiple cases. Each case describes one polygon. It starts with an integer n <= 50, the number of vertices in the polygon, followed by three pairs of real numbers giving the x and y coordinates of three vertices of the polygon. The numbers are separated by whitespace. The input ends with a n equal 0, this case should not be processed.

For each line of input, output one line in the format shown below, giving the smallest area of a rectangle which can cover all the vertices of the polygon and whose sides are parallel to the x and y axes.

4
10.00000 0.00000
0.00000 -10.00000
-10.00000 0.00000
6
22.23086 0.42320
-4.87328 11.92822
1.76914 27.57680
23
156.71567 -13.63236
139.03195 -22.04236
137.96925 -11.70517
0


Polygon 1: 400.000
Polygon 2: 1056.172
Polygon 3: 397.673


/* @author: */
import java.util.Scanner;
public class Main{
public static void main(String args[])
{
Scanner sc=new Scanner(System.in);
int n;
double xx1,xx2,xx3,yy1,yy2,yy3,x,y,mnx,mxx,mny,mxy;

int t=1;
while(sc.hasNext())
{
n=sc.nextInt();
if(n==0) break;
xx1=sc.nextDouble();
yy1=sc.nextDouble();
xx2=sc.nextDouble();
yy2=sc.nextDouble();
xx3=sc.nextDouble();
yy3=sc.nextDouble();
double A1=2*(xx1-xx2);
double A2=2*(xx1-xx3);
double B1=2*(yy1-yy2);
double B2=2*(yy1-yy3);
double C1=xx1*xx1+yy1*yy1-xx2*xx2-yy2*yy2;
double C2=xx1*xx1+yy1*yy1-xx3*xx3-yy3*yy3;
double J=A1*B2-A2*B1;
x=(C1*B2-C2*B1)/J;
y=(A1*C2-A2*C1)/J;
mnx=mny=999999999;
mxx=mxy=-999999999;
double angle=2*3.14159265358979/n;
double xx,yy;
for(int i=0;i< n;i++)
{
xx=Math.cos(i*angle)*(xx1-x)-Math.sin(i*angle)*(yy1-y)+x;
yy=Math.sin(i*angle)*(xx1-x)+Math.cos(i*angle)*(yy1-y)+y;
if(xx< mnx)mnx=xx;
if(xx>mxx)mxx=xx;
if(yy< mny)mny=yy;
if(yy>mxy)mxy=yy;
}
mxx=mxx-mnx;
mxy=mxy-mny;
System.out.printf("Polygon %d: %.3f\n",t,mxx*mxy);
t++;
}
}
}

1. 题本身没错，但是HDOJ放题目的时候，前面有个题目解释了什么是XXX定律。
这里直接放了这个题目，肯定没几个人明白是干啥

2. 您没有考虑 树的根节点是负数的情况， 若树的根节点是个很大的负数，那么就要考虑过不过另外一边子树了