POJ 2079 Triangle（回転チャック）

3906 ワード
幾何学を計算する チャックを回す
POJ 2079 Triangle（回転チャック）：http://poj.org/problem?id=2079
タイトルの説明:
Triangle
Time Limit: 3000 MS
 
メモリLimit: 30000 K
Total Submissions: 9131
 
Acceepted: 2704
Description
Given distinct points on a pline、your task is to find the triangle that have the maximure ara、whose vertices are from the given points.
Input
The input consists of several test cases.The first line of each test case contains an integer n，indicating the number of points on the pline.Each of the following ingline s two integer xi and y，indicating the Point ingline.ingline.insts.ingline.inits。which shound not be processed.You may asume that 1<=n==50000 and−10
4 <= xi，yi<=10
4 for all i=1..n.
Output
For each test case，print a line containing the maximure ara，which contains two digits after the decimal point.You may assie that the is always an answer which is greater thanゼロ.
Sample Input
3
3 4
2 6
2 7
5
2 6
3 9
2 0
8 0
6 5
-1
Sample Output
0.50
27.00
タイトルの大意:
平面上のn個の点を与えて，これらの点を頂点とする三角形の最大面積の一つを見出し，その面積を出力する。
アルゴリズム解析:
最大の三角形は常に凸包の頂点で囲まれていますので、先に凸包を作ってもいいですが、直接に凸包の頂点を数えると計算効率が低くなり、タイムアウトします。ここでは回転カードケースのアルゴリズムを使ってこの問題を解決します。
まず、三角形の第1の頂点iを列挙し、第2の頂点j=i＋1と第3の頂点k=j＋1を初期化し、Area(i，j，k)>Area(i，j，k+1)までを循環して実行し、最大面積を更新し、j，kの2つの点を回転し、Area(i，j，k)コードの実装:
#include <iostream>
#include <algorithm>
#include <cstdio>

#define N 50005
#define max(a,b) a>b?a:b

using namespace std;

struct node
{
    int x,y;
}dd[N];

int n,stak[N],top,top1;
bool cmp(node a,node b)
{
    return a.x<b.x||(a.x==b.x && a.y<b.y);
}
bool judege_right(int o,int a,int b)
{
    int ax=dd[a].x-dd[o].x;
    int bx=dd[b].x-dd[o].x;
    int ay=dd[a].y-dd[o].y;
    int by=dd[b].y-dd[o].y;
    return bx*ay>ax*by;
}

double area(int o,int a,int b)
{
    int ax=dd[a].x-dd[o].x;
    int bx=dd[b].x-dd[o].x;
    int ay=dd[a].y-dd[o].y;
    int by=dd[b].y-dd[o].y;
    return abs(bx*ay-ax*by)*1.0/2.0;
}

void build_map()
{
    int i;
    top=0;
    sort(dd,dd+n,cmp);
    stak[top++]=0;
    stak[top++]=1;
    for(i=2;i<n;i++)
    {
        stak[top++]=i;
        while(top>=3)
        {
            if(judege_right(stak[top-3],stak[top-2],stak[top-1]))
                break;
            stak[top-2]=stak[top-1];
            top--;
        }
    }
    top1=top;
    stak[top++]=n-2;
    for(i=n-3;i>=0;i--)
    {
        stak[top++]=i;
        while(top-top1>=2)
        {
            if(judege_right(stak[top-3],stak[top-2],stak[top-1]))
                break;
            stak[top-2]=stak[top-1];
            top--;
        }
    }
    top--;
}
int main()
{
    int i,j,k;
    while(scanf("%d",&n)!=EOF)
    {
        if(n==-1)
        {
            break;
        }
        for(i=0;i<n;i++)
        {
            scanf("%d%d",&dd[i].x,&dd[i].y);
        }
        build_map();
        double ans=0;
        for(i=0;i<top;i++)
        {
            j=(i+1)%top;
            k=(j+1)%top;
            while(k!=i&&area(stak[i],stak[j],stak[k])<area(stak[i],stak[j],stak[(k+1)%top]))
            {
                k=(k+1)%top;
            }
            if(k==i)
                continue;
            int kk=(k+1)%top;
            while(j!=kk&&k!=i)
            {
                ans=max(ans,area(stak[i],stak[j],stak[k]));
                while(k!=i&&area(stak[i],stak[j],stak[k])<area(stak[i],stak[j],stak[(k+1)%top]))
                {
                    k=(k+1)%top;
                }
                j=(j+1)%top;
            }
        }
        printf("%.2lf
",ans);
    }
    return 0;
}
Android wifi休眠戦略
ネットワークタイムスタンプを要求します。