[POJ 2079] | Eurce's Blog

旋转卡壳

题意：给出最多50000个点，可取任意3点作三角形，求这些三角形中得面积最大值。

首先，可以明确的是三角形的三个顶点必定在凸包上。求出凸包后，点的数量减少到O(n^2)算法可解。

然后，需要考虑的是最大面积三角形的三点会以何种形式出现。一开始考虑的是对于所有的对踵边，枚举其对应的所有三角形，但是WA。后来发现，三角形的三边可以都不为对踵边。应该枚举的是各个点对应的最大三角形面积。在求顶点i对应的最大三角形面积时，要依次求出当j取其余n-1个点时对应的最大三角形面积，因此，可以构造如下算法：

0. 初始化顶点i为第一个顶点：
1. 初始化j为i在凸包上的下一个顶点
2. 取k为使area(i,j,k)最大的顶点，更新最大面积
3. 当j!=i时，取j为下一个顶点，回到2.；否则取i为下一个顶点，若未取尽，回到1.

其中第3步计算k时，容易利用旋转卡壳的思想证明如下结论：边(i,j+1)对应的k，必定在边(i,j)对应的k之后。由此，对于某个i，其对应的j和k的总自增次数都是O(n)级别的，总体复杂度便是O(n^2)。

#include<cmath>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;

#define eps 1e-8
#define nt(i) (i==n?0:i)

int n;
int stk[50000],sl;
double mx;

struct E
{
    double x,y,a,r;
    bool operator < (const E &p) const
    {
        return a<p.a;
    }
}e[50001];

double crs(double x1,double y1,double x2,double y2)
{
    return x1*y2-x2*y1;
}

double area(int i,int j,int k)
{
    double x1=e[i].x,y1=e[i].y;
    double x2=e[j].x,y2=e[j].y;
    double x3=e[k].x,y3=e[k].y;
    return abs(crs(x2-x1,y2-y1,x3-x1,y3-y1))/2;
}

void init()
{
    int i,j,k,l;
    sl=0;
    mx=0;
    double xm=0,ym=0;
    double x1,y1,x2,y2,x3,y3;
    for(i=0;i<n;i++)
    {
        scanf("%lf%lf",&e[i].x,&e[i].y);
        xm+=e[i].x;
        ym+=e[i].y;
    }
    xm/=n;
    ym/=n;
    for(i=0;i<n;i++)
    {
        e[i].x-=xm;
        e[i].y-=ym;
        e[i].a=atan2(e[i].y,e[i].x);
        e[i].r=sqrt(pow(e[i].y,2)+pow(e[i].x,2));
    }
    sort(e,e+n);
    for(i=j=0;i<n;i++)
    {
        if(e[i].r>e[j].r)
            j=i;
    }
    reverse(e,e+j);
    reverse(e+j,e+n);
    reverse(e,e+n);
    e[n++]=e[0];
    stk[sl++]=0;
    stk[sl++]=1;
    for(i=2;i<n;i++)
    {
        if(sl<2)
        {
            stk[sl++]=i;
            continue;
        }
        x1=e[i].x; y1=e[i].y;
        while(sl>1)
        {
            j=stk[sl-1];
            k=stk[sl-2];
            x2=e[j].x; y2=e[j].y;
            x3=e[k].x; y3=e[k].y;
            if(crs(x2-x3,y2-y3,x1-x2,y1-y2)>eps)
                break;
            sl--;
        }
        stk[sl++]=i;
    }
    for(i=0;i<sl-1;i++)
        e[i]=e[stk[i]];
    n=sl-1;
}

void solve()
{
    int i,j,k;
    double u,v;
    for(i=0;i<n;i++)
    {
        for(j=nt(i+1),k=nt(j+1);j!=i;j=nt(j+1))
        {
            u=area(i,j,k);
            while(k!=i&&u<(v=area(i,j,nt(k+1))))
            {
                k=nt(k+1);
                u=v;
            }
            mx=max(mx,u);
        }
    }
    printf("%.2f\n",mx);
}

int main()
{
    while(~scanf("%d",&n)&&~n)
    {
        init();
        solve();
    }
    return 0;
}

100

101

102

103

104

105

106

107

108

109

110

111

112

113

114

115

116

117

118

119

120

121

122

123

#include<cmath>

#include<cstdio>

#include<cstring>

#include<algorithm>

using namespace std;

#define eps 1e-8

#define nt(i) (i==n?0:i)

int n;

int stk[50000],sl;

double mx;

struct E

{

double x,y,a,r;

bool operator < (const E &p) const

{

return a<p.a;

}

}e[50001];

double crs(double x1,double y1,double x2,double y2)

{

return x1*y2-x2*y1;

}

double area(int i,int j,int k)

{

double x1=e[i].x,y1=e[i].y;

double x2=e[j].x,y2=e[j].y;

double x3=e[k].x,y3=e[k].y;

return abs(crs(x2-x1,y2-y1,x3-x1,y3-y1))/2;

}

void init()

{

int i,j,k,l;

sl=0;

mx=0;

double xm=0,ym=0;

double x1,y1,x2,y2,x3,y3;

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

{

scanf("%lf%lf",&e[i].x,&e[i].y);

xm+=e[i].x;

ym+=e[i].y;

}

xm/=n;

ym/=n;

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

{

e[i].x-=xm;

e[i].y-=ym;

e[i].a=atan2(e[i].y,e[i].x);

e[i].r=sqrt(pow(e[i].y,2)+pow(e[i].x,2));

}

sort(e,e+n);

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

{

if(e[i].r>e[j].r)

j=i;

}

reverse(e,e+j);

reverse(e+j,e+n);

reverse(e,e+n);

e[n++]=e[0];

stk[sl++]=0;

stk[sl++]=1;

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

{

if(sl<2)

{

stk[sl++]=i;

continue;

}

x1=e[i].x; y1=e[i].y;

while(sl>1)

{

j=stk[sl-1];

k=stk[sl-2];

x2=e[j].x; y2=e[j].y;

x3=e[k].x; y3=e[k].y;

if(crs(x2-x3,y2-y3,x1-x2,y1-y2)>eps)

break;

sl--;

}

stk[sl++]=i;

}

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

e[i]=e[stk[i]];

n=sl-1;

}

void solve()

{

int i,j,k;

double u,v;

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

{

for(j=nt(i+1),k=nt(j+1);j!=i;j=nt(j+1))

{

u=area(i,j,k);

while(k!=i&&u<(v=area(i,j,nt(k+1))))

{

k=nt(k+1);

u=v;

}

mx=max(mx,u);

}

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

}

int main()

{

while(~scanf("%d",&n)&&~n)

{

init();

solve();

}

return 0;

}