求n条边能围成的最大面积.txt

解决排列组合问题的通用算法,自然数得拆分,求最大公约数的算法

ACM/ICPC 试题解析 
 
作者：熊蜀光 文章来源：哈尔滨工业大学 数据库研究中心 点击数：2152 更新时间：2004-11-5 
纯C论坛·电子杂志第一期文章
(PDF下载)
http://purec.binghua.com/Soft/Class2/dl_hpcem/200410/74.html
（转载请注名原作者及出处）



--------------------------------------------------------------------------------

ACM/ICPC 试题解析

哈尔滨工业大学数据库研究中心 熊蜀光

 

孔子和耶稣都说过，算法是程序设计的灵魂（开个玩笑），由此可见算法理论的重要性，然而我们也不能纸上谈兵，必须动手实践，这对于编程和思维能力都会有好处。希望本栏目能对大家有所帮助（编者按：同时也迫切地希望大家多多投稿，多提意见）。好了，闲话休提，让我们来看看一个纯算法设计的题目吧。这道题来自浙江大学的ACM/ICPC在线评判网站(http://acm.zju.edu.cn)，关于ACM/ICPC的介绍请见后文。

Fence


--------------------------------------------------------------------------------

Time limit: 1 Seconds   Memory limit: 32768K   
Total Submit: 532   Accepted Submit: 134   


--------------------------------------------------------------------------------

Workers are going to enclose a new working region with a fence. For their convenience the enclosed area has to be as large as possible. They have N rectangular blocks to build the fence. The length of the i-th block is Li meters. All blocks have the same height of 1 meter. The workers are not allowed to break blocks into parts. All blocks must be used to build the fence.
Input

The first line of the input file contains one integer N (3 <= N <= 100).The following N lines describe fence blocks. Each block is represented by its length in meters (integer number, 1 <= Li <= 100).Process to the end of file.
Output

Write to the output file one non-negative number S - maximal possible area of the working region (in square meters). S must be written with two digits after the decimal point. If it is not possible to construct the fence from the specified blocks, write 0.00.
Sample Input

4
10
5
5
4
3
8
5
5
3
10
5
4
Sample Output

28.00
12.00
0.00

这是一道几何题，已知N条线段，每条线段长度为Li，求它们能围成的多边形的最大面积，并精确到小数点后两位输出，如果不能围成多边形，则直接输出0.00。

分析：

初看这道题目，似乎无从下手，我们首先对简单情况讨论。

对于3条线段，则围成的面积是固定的，只需判定短的两边之和是否大于第三边，然后根据海伦公式可求出面积。

对于4条线段，显然能围成四边形的充要条件是最长边小于其余边长的和，那么如果满足此条件，又如何确定面积的最大值呢？



图一

设其中的一条对角线长为X(图一)，显然四边形面积可以表示为X的函数，再对该函数求导得0建立方程，可求出X的值和最大面积的数值解，但是用这种方法求解时表达式过于繁琐，何况我们只需求出近似解即可，所以考虑其它的方法。

假想由4条边围成的一个很薄的盒子，顶点处可以自由转动，里面充满气体，盒子外面为真空，那么由于内部气体的压力，盒子会发生形变，最终会处于静力平衡状态，那么在这个状态下，气体的压强达到可能的最低，倘若不是，那么气体必然会向压强减小的方向膨胀。由于气体的质量不变，所以此时的盒子面积最大。在这种情况下，由于气体的各处压强相同，每边受力是均匀的，所以可以将受力转化为一个作用在各边中点，并垂直于相应边的力。因为不可能出现三边都平行的情况，所以必能找到三条边，使它们的中垂线两两相交，设作用在这三边的力分别为F1,F2,F3，固定剩下的一边于地面上，设F1与F3的交点为A，F2与F3的交点为B(图二)，对A点取力矩，则F1和F3作用在A点的力矩均为0，F2作用在A点的力矩不为0，所以不能达到平衡，所以A点和B点必定重合。所以此三边的中垂线交于一点，所以这个四边形的顶点共圆。



图二

对于N条线段，假设它们已经围成了一个面积最大的多边形，那么取相邻的4个顶点围成的四边形(图三)，必然也是这4边围成的四边形中面积最大的，否则我们还能由这4边围成一个面积更大的四边形，那么所形成的新多边形面积大于目前的多边形，矛盾。所以这4个相邻顶点共圆，那么接下来的4个顶点也共圆，由3点确定一个圆可知，这5点共圆。因此，所有的N个点共圆。



图三

现在就可以有很多方法求面积了，我们采用先求外接圆的半径，再利用海伦公式求各个以半径分割的三角形面积，再求和得到多边形面积的方法(图四)。



图四                                      图五

求半径可以采用解析方法，但是同样繁琐，我们采用二分逼近的数值方法。首先确定半径的范围，显然大于等于最大边长的1/2，小于线段长度和的1/2(当然还可以更小，这里只考虑了能够围成多边形这一基本条件)。首先令R为最大边长的1/2，要考虑三种情况：圆心在多边形内部(图四)，圆心在多边形外部(图五)，圆心是最大边的中点。可以用其余边对R的圆心角之和与Pi来判断：如果大于，则圆心必定在多边形内部，如若不然，因为实际的半径大于等于R，而圆心在多边形外部，所以其余边对实际半径的圆心角必小于Pi，矛盾。同理可证圆心在多边形外部的情况。圆心是最大边中点的情况可直接求出半径。在这个范围内以半径R作迭代，R每次取上下界的中值。

圆心在多边形内部时，由于R与圆心角之和增减性相同，所以到算出的所有边的圆心角之和在误差范围内等于2*Pi停止，此时的R就是所求半径。再根据半径求面积即可。

圆心在多边形外部时，倘若除去最长边的其余各边的圆心角sum的和小于最长边的圆心角a，则根据圆心角的变化规律不难看出，所求半径比当前半径R要小；否则所求半径比当前半径R大，到算出sum与a在误差范围内相等时停止。面积为除去最长边的其余各边所对应的三角形面积和减去最长边为底边的三角形面积。

 

注：2003年ACM/ICPC北京赛区的B题跟此题类似。

附：程序源代码

///                     求n条已知长度的线段围成的最大面积              ///

///                                                                    ///

#include "stdio.h"

#include "iostream.h"

#include "math.h"

#include <algorithm>

using namespace std;

 

const double pi=3.1415926535898;

const double small=0.00000000001;

double l[200];

int n;

 

double halen(double a,double b,double c)

{

     double s=(a+b+c)/2.0;

     return sqrt(s*(s-a)*(s-b)*(s-c));

}

 

double angle_small(double r)

{

     int i;

     double angle=0.0;

     for(i=0;i<n-1;i++)

     {

         angle+=2*asin(l[i]/2.0/r);

     }

     return angle;

}

 

double angle_all(double r)

{

     int i;

     double angle=0.0;

     for(i=0;i<n;i++)

     {

         angle+=2*asin(l[i]/2.0/r);

     }

     return angle;

}

 

int main(void)

{

     int i;

     double r,max,min,sum,area;

     while(cin>>n)

     {

         sum=0.0;

         for(i=0;i<n;i++)

         {

              cin>>l[i];

              sum+=l[i];

         }

         sort(l,l+n);

         if(sum-l[n-1]<l[n-1])

         {

              printf("0.00\n");

              continue;

         }

         min=l[n-1]/2.0;max=sum/2.0;area=0.0;

         if(angle_small(l[n-1]/2.0)>pi-small) 

         {

              while(true)

              {

                   r=(min+max)/2.0;

                   if(angle_all(r)<2.0*pi-small)

                   {

                       max=r;

                   }

                   else if(angle_all(r)>2.0*pi+small)

                   {

                       min=r;

                   }

                   else

                   {

                       break;

                   }

              }

              for(i=0;i<n;i++)

              {

                   area+=halen(l[i],r,r);

              }

         }

         else if(angle_small(l[n-1]/2.0)<pi-small)

         {

              max=1000000000;

              while(true)

              {

                   r=(min+max)/2.0;

                   if(angle_small(r)<2*asin(l[n-1]/2.0/r)-small)

                   {

                       min=r;

                   }

                   else if(angle_small(r)>2*asin(l[n-1]/2.0/r)+small)

                   {

                       max=r;

                   }

                   else

                   {

                       break;

                   }

              }

              for(i=0;i<n-1;i++)

              {

                   area+=halen(l[i],r,r);

              }

              area-=halen(l[n-1],r,r);

         }

         else

         {

              r=l[n-1]/2.0;

              for(i=0;i<n-1;i++)

              {

                   area+=halen(l[i],r,r);

              }

         }

         printf("%.2f\n",area);

     }

     return 0;

}