2013
11-10

# Area in Triangle

Given a triangle field and a rope of a certain length (Figure-1), you are required to use the rope to enclose a region within the field and make the region as large as possible.

The input has several sets of test data. Each set is one line containing four numbers separated by a space. The first three indicate the lengths of the edges of the triangle field, and the fourth is the length of the rope. Each of the four numbers have exactly four digits after the decimal point. The line containing four zeros ends the input and should not be processed. You can assume each of the edges are not longer than 100.0000 and the length of the rope is not longer than the perimeter of the field.

Output one line for each case in the following format:

Case i: X

Where i is the case number, and X is the largest area which is rounded to two digits after the decimal point.

12.0000 23.0000 17.0000 40.0000
84.0000 35.0000 91.0000 210.0000
100.0000 100.0000 100.0000 181.3800
0 0 0 0


Case 1: 89.35
Case 2: 1470.00
Case 3: 2618.00


/* @author: */
import java.util.Scanner;
public class Main {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);

int k = 1;
double l1, l2, l3, s, c, p, R, ctg1, ctg2, ctg3, len, r, ls, area;

while( sc.hasNext() )
{
l1=sc.nextDouble();
l2=sc.nextDouble();
l3=sc.nextDouble();
len=sc.nextDouble();
if( l1 == 0 && l2 == 0 && l3 == 0 && len == 0 )
break;

c = l1 + l2 + l3;
p = ( l1 + l2 + l3 ) / 2;
s = Math.sqrt( p * (p-l1) * (p-l2) * (p-l3) );

if( len >= c )
{
System.out.printf( "Case %d: %.2f\n", k++, s );
continue;
}
R = s * 2 / c ;
if( len <= R * 2 * Math.PI )
{
System.out.printf( "Case %d: %.2f\n", k++, len*len / (4*Math.PI) );
continue;
}
ctg1 = ( p - l1 ) / R;
ctg2 = ( p - l2 ) / R;
ctg3 = ( p - l3 ) / R;
r = ( c - len ) / ( 2 * ( ctg1 + ctg2 + ctg3 ) - 2 * Math.PI );
ls = c - 2 * ( ctg1 + ctg2 + ctg3 ) * r;
l1 -= ( ctg2 + ctg3 ) * r;
l2 -= ( ctg1 + ctg3 ) * r;
l3 -= ( ctg1 + ctg2 ) * r;
p = ( l1 + l2 + l3 ) / 2;
area = ls * r + Math.sqrt( p * (p-l1) * (p-l2) * (p-l3) ) + r * r * Math.PI;
System.out.printf( "Case %d: %.2f\n", k++, area );
}
}
}

1. 5.1处，反了；“上一个操作符的优先级比操作符ch的优先级大，或栈是空的就入栈。”如代码所述，应为“上一个操作符的优先级比操作符ch的优先级小，或栈是空的就入栈。”

2. 约瑟夫也用说这么长……很成熟的一个问题了，分治的方法解起来o(n)就可以了，有兴趣可以看看具体数学的第一章，关于约瑟夫问题推导出了一系列的结论，很漂亮

3. 有一点问题。。后面动态规划的程序中
int dp[n+1][W+1];
会报错 提示表达式必须含有常量值。该怎么修改呢。。