2013
11-11

# Angle and Squares

Here is a geometric problem. You have an angle and some squares in the first quadrant of the plane rectangular coordinates. The vertex of the angle is fixed on the origin O of the coordinates, and both of its radial lines are specified by the input. The sizes of the squares are also specified by the input, and the squares can shift vertically and horizontally. Now your job is to use the squares and the radial lines of the angle to enclose the maximum area, which excludes the area of the squares (see Figure 1). You should note that the edges of the squares must be parallel to the axes.

Figure 1

There are several test cases. Each test case starts with a line consisting of one positive integer N (0 < N < 10), which is the number of the squares. The next line contains four decimal numbers: xa, ya, xb, yb, which denote two points A (xa, ya) and B (xb, yb). The radial lines OA and OB form the angle. Each of the following N lines contains a decimal number, which is the edge length of a square. All the decimal numbers mentioned above are in the range [1, 20]. A test case with N = 0 ends the input, and should not be processed.

For each data case, output one line containing a decimal number, which is the maximum area that can be enclosed by the radial lines of the angle and the squares. The value should be rounded to three digits after the decimal point.

1
2.000 3.000 3.000 2.000
1.000
0


2.000

/* @author: */
import java.util.Scanner;
public class Main {

public static void main(String[] args) {
Scanner sc = new Scanner(System.in);

double angle,p,a,b,c,t,l,xa,xb,ya,yb,k1,k2,x1,x2,y1,y2,l2;
int n,i;
while(sc.hasNext())
{
n=sc.nextInt();
if(n==0) break;
xa=sc.nextDouble();
ya=sc.nextDouble();
xb=sc.nextDouble();
yb=sc.nextDouble();
l=l2=0;
for(i=0;i< n;i++)
{
t=sc.nextDouble();
l+=t;
l2+=t*t/2;
}
k1=ya/xa;k2=yb/xb;
x1=l*(1+k2)/(k1-k2);x2=l*(1+k1)/(k1-k2);
y1=k1*x1;y2=k2*x2;
a=Math.sqrt(x1*x1+y1*y1);b=Math.sqrt(x2*x2+y2*y2);c=Math.sqrt(2)*l;
p=0.5*(a+b+c);
System.out.printf("%5.3f\n",Math.sqrt(p*(p-a)*(p-b)*(p-c))-l2);
}
}
}