http://poj.org/problem?id=2079 (题目链接)
题意
求凸包内最大三角形面积
Solution
旋转卡壳。
只会n²的做法，但是竟然过了。就是枚举每一个点，然后旋转卡壳另外两个点。先固定i，j这2个邻接的顶点。然后找出使三角形面积最大的那个k点。然后再固定i，枚举j点，由于k点是随着j点的变化在变化，所以k点不必从开头重新枚举。
之后去网上看了下O（n）的做法，当时就感觉有点鬼，打了一遍交上去Wa了，鬼使神差拍出一组数据好像可以把网上O（n）的做法全部卡掉，但是我也还搞不清为什么这样做是错的。
数据：
5
-7 0
-5 1
-1 5
-2 8
5
0 7
1 5
5 1
8 2
4 8
5
0 -7
4 -8
8 -2
5 -1
1 -5
-1
这3个数据都是同一个凸包，面积都是15.00。
O(n)代码
// poj2079
#include<algorithm>
#include<iostream>
#include<cstring>
#include<cstdlib>
#include<cstdio>
#include<cmath>
#include<map>
#define esp 1e-8
#define inf 2147483640
#define LL long long
#define Pi acos(-1.0)
#define free(a) freopen(a".in","r",stdin);freopen(a".out","w",stdout);
using namespace std;
inline LL getint() {
LL x=0,f=1;char ch=getchar();
while (ch>'9' || ch<'0') {if (ch=='-') f=-1;ch=getchar();}
while (ch>='0' && ch<='9') {x=x*10+ch-'0';ch=getchar();}
return x*f;
}
const int maxn=50010;
struct point {int x,y;}p[maxn],p0;
int cross(point p0,point p1,point p2) {
return (p1.x-p0.x)*(p2.y-p0.y)-(p2.x-p0.x)*(p1.y-p0.y);
}
double dis(point a,point b) {
return sqrt((double)(a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y));
}
bool cmp(point a,point b) {
int t=cross(p0,a,b);
if (t>0) return 1;
if (t<0) return 0;
return dis(p0,a)<dis(p0,b);
}
int Graham(int n) {
if (n==1) return 1;
int k=1,top=2;
for (int i=1;i<=n;i++)
if (p[i].y==p[k].y ? p[i].x<p[k].x : p[i].y<p[k].y) k=i;
p0=p[k];p[k]=p[1];p[1]=p0;
sort(p+2,p+1+n,cmp);
for (int i=3;i<=n;i++) {
while (top>1 && cross(p[top-1],p[top],p[i])<=0) top--;
p[++top]=p[i];
}
return top;
}
double RC(int n) {
int ans=0;
p[n+1]=p[1];
int i=1,j=2,k=3,t;
while (k!=1) {
int ii=i,jj=j,kk=k;
while ((t=abs(cross(p[i],p[k],p[j])))<abs(cross(p[i],p[k+1],p[j]))) k=k%n+1;
ans=max(ans,t);
while ((t=abs(cross(p[i],p[k],p[j])))<abs(cross(p[i],p[k],p[j+1]))) j=j%n+1;
ans=max(ans,t);
while ((t=abs(cross(p[i],p[k],p[j])))<abs(cross(p[i+1],p[k],p[j]))) i=i%n+1;
ans=max(ans,t);
if (ii==i && jj==j && kk==k) k=k%n+1;
}
return (double)ans/2.0;
}
int main() {
int n;
while (scanf("%d",&n)!=EOF && n>0) {
for (int i=1;i<=n;i++) scanf("%d%d",&p[i].x,&p[i].y);
n=Graham(n);
printf("%.2f
",RC(n));
}
return 0;
}
O（n²）代码
// poj2079
#include<algorithm>
#include<iostream>
#include<cstring>
#include<cstdlib>
#include<cstdio>
#include<cmath>
#include<map>
#define esp 1e-8
#define inf 2147483640
#define LL long long
#define Pi acos(-1.0)
#define free(a) freopen(a".in","r",stdin);freopen(a".out","w",stdout);
using namespace std;
inline LL getint() {
LL x=0,f=1;char ch=getchar();
while (ch>'9' || ch<'0') {if (ch=='-') f=-1;ch=getchar();}
while (ch>='0' && ch<='9') {x=x*10+ch-'0';ch=getchar();}
return x*f;
}
const int maxn=50010;
struct point {int x,y;}p[maxn],p0;
int cross(point p0,point p1,point p2) {
return (p1.x-p0.x)*(p2.y-p0.y)-(p2.x-p0.x)*(p1.y-p0.y);
}
double dis(point a,point b) {
return sqrt((double)(a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y));
}
bool cmp(point a,point b) {
int t=cross(p0,a,b);
if (t>0) return 1;
if (t<0) return 0;
return dis(p0,a)<dis(p0,b);
}
int Graham(int n) {
if (n==1) return 1;
int k=1,top=2;
for (int i=1;i<=n;i++)
if (p[i].y==p[k].y ? p[i].x<p[k].x : p[i].y<p[k].y) k=i;
p0=p[k];p[k]=p[1];p[1]=p0;
sort(p+2,p+1+n,cmp);
for (int i=3;i<=n;i++) {
while (top>1 && cross(p[top-1],p[top],p[i])<=0) top--;
p[++top]=p[i];
}
return top;
}
double RC(int n) {
int ans=0;
p[n+1]=p[1];
for (int i=1;i<=n;i++) {
int j=i%n+1,k=(i+1)%n+1;
while (abs(cross(p[i],p[j],p[k]))<abs(cross(p[i],p[j],p[k+1]))) k=k%n+1;
while (i!=j && i!=k) {
ans=max(ans,abs(cross(p[i],p[j],p[k])));
while (abs(cross(p[i],p[j],p[k]))<abs(cross(p[i],p[j],p[k+1]))) k=k%n+1;
j=j%n+1;
}
}
return (double)ans/2.0;
}
int main() {
int n;
while (scanf("%d",&n)!=EOF && n>0) {
for (int i=1;i<=n;i++) scanf("%d%d",&p[i].x,&p[i].y);
n=Graham(n);
printf("%.2f
",RC(n));
}
return 0;
}