[技巧的列挙]ZOJ 3672 Pan's Labyrine th

テーマリンク:
http://acm.zju.edu.cn/onlinejudge/showProblem.do?problemCode=3762
Pan's Labyrine th
Time Limit: 2 Seconds     
メモリLimit: 65536 KB     
Special Jundge
Ofelia is chased by her evil stepfather，and now she finds hers herelf lost in a labyrine.She needs your help to run away from hers trgic family.
The e e's a huge metal door standing in front of the exit of the labyrith.The re are n dots on the metal door.Pan(the god of the labyrine)asks Ofelia to find out a triangle which has the larget height.The triangle's three vertexs must the dots dots、and its aremust the polive。
Input
The re are multiple cases.For each case，the first line contains an integer n (3<=n<=500）.In the next nライン、each line contains two real number x[i] y[i] (0<=x[i]，y[==10000]which indicates each dot's coordinate.The e e isのtwo dots in the same coordinate.The answers are stritly greater than 0.
Output
For each test case，output one line with the maximtriangle height.Any solution with a relative or absolution error of at most 1 e-6 will be accepted.
Sample Input

6
0.000 4.000
2.000 4.000
1.000 0.000
1.000 8.000
0.900 7.000
1.100 7.000
7
6967.54555 3457.71200
3.52325 1273.85912
7755.35733 9812.97643
753.00303 2124.70937
7896.71246 8877.78054
5832.77264 5213.70478
4629.38110 8159.01498

Sample Output

7.00000
8940.96643

ベント
In case 1.Choose the 
dot 3,5,6
 to make up a triangle，and this triangle has the larget height 7.000.In case 2.We chose dot 2,3,5.
タイトルの意味：
n個の点をあげて、3つの点を選んで三角形を作って、一番長い高さを求めます。
問題解決の考え方：
一番長い三角形の底辺の二点には、頂点から一番遠い点があります。証明書:http://blog.csdn.net/synapse7/article/details/20942443 一番遠い点を先に処理して、far[i]は点iから一番遠い点を表して、o(n)はその中の一つを列挙して、o(1)は最も遠い点を探して、またo(n)は別の点を列挙します。
叉積は面積を求めて、更に高いことを求めます。
コード:

//#include<CSpreadSheet.h>

#include<iostream>
#include<cmath>
#include<cstdio>
#include<sstream>
#include<cstdlib>
#include<string>
#include<string.h>
#include<cstring>
#include<algorithm>
#include<vector>
#include<map>
#include<set>
#include<stack>
#include<list>
#include<queue>
#include<ctime>
#include<bitset>
#include<cmath>
#define eps 1e-6
#define INF 0x3f3f3f3f
#define PI acos(-1.0)
#define ll __int64
#define LL long long
#define lson l,m,(rt<<1)
#define rson m+1,r,(rt<<1)|1
#define M 1000000007
//#pragma comment(linker, "/STACK:1024000000,1024000000")
using namespace std;

#define Maxn 550

struct Point
{
    double x,y;
}pp[Maxn];
double dis[Maxn][Maxn];
int far[Maxn],n; //far[i]            

double Cal(int i,int j) //       
{
    return sqrt((pp[i].x-pp[j].x)*(pp[i].x-pp[j].x)+(pp[i].y-pp[j].y)*(pp[i].y-pp[j].y));

}

double Cha(Point a,Point b) //         
{
    return a.x*b.y-a.y*b.x;
}

double solve(int a,int b,int c)
{
    Point aa,bb;
    aa.x=pp[a].x-pp[b].x,aa.y=pp[a].y-pp[b].y;
    bb.x=pp[c].x-pp[b].x,bb.y=pp[c].y-pp[b].y;

    double are=abs(Cha(aa,bb)); //   2 

    return max(are/dis[a][b],max(are/dis[a][c],are/dis[b][c])); //    

}

int main()
{
   //freopen("in.txt","r",stdin);
   //freopen("out.txt","w",stdout);
   while(~scanf("%d",&n))
   {
       for(int i=1;i<=n;i++)
            scanf("%lf%lf",&pp[i].x,&pp[i].y);
       for(int i=1;i<=n;i++) //             
       {
           double dd=-1;
           int re;

           for(int j=1;j<=n;j++)
           {
               if(i==j)
                    continue;
               double temp=Cal(i,j);
               dis[i][j]=temp;

               if(temp>dd)
               {
                   dd=temp;
                   re=j;
               }
           }
           far[i]=re;
       }
       double ans=-1;

       for(int i=1;i<=n;i++)
       {
           int ff=far[i];

           for(int j=1;j<=n;j++)
           {
               if(j==i||j==ff)
                    continue;
               double temp=solve(i,j,ff);
               if(temp>ans)
                   ans=temp;
           }
       }
       printf("%.6lf
",ans);
   }

   return 0;
}