zoj 2419 poj 2079 求点集中面积最大的三角形
网上很多的做法都是暴力枚举的，数据太水了才会过，下面的做法是O（n）的，但是没有严格的证明
先枚举一条边(i,j)，再枚举一个点k，让点k一直跑，跑到最远为止。（凸包的单调性）
固定边（ i ，k），枚举j，。。。。。。。。。。。。。。。。
固定（j、k），。。。。。。。。。。。。。。。。。。。。。。。
注意每一次旋转结束后需要更新面积的最大值（如果能更新）
如果一次下来 i,j,k都在原来的地方没有动过，就让k往后挪一个位置
直到k到了第一个点程序终止
View Code
#include <math.h>
#include <cstdio>
#include<algorithm>
using namespace std;
const int maxn = 100010;
struct point{
double x,y;
}p[maxn],set[maxn];
const double eps = 1e-8;
int max(int x,int y){return x>y?x:y;}
double max(double x,double y) {return ((x)>(y)?(x):(y));}
double sgn(double x) {return (fabs(x)<eps?0:(x>0?1:-1));}
bool cmp(point a,point b) {return (a.x<b.x || sgn(a.x-b.x)==0 && a.y<b.y);}
double cross(point a,point b,point c){return (b.x-a.x)*(c.y-a.y)-(b.y-a.y)*(c.x-a.x);}
double s[maxn];
int tot;
void hull(int l,int r,point a,point b){
int x=l,i=l-1,j=r+1,k;
for (k=l;k<=r;k++){
double temp=sgn(s[x]-s[k]);
if (temp<0 || temp==0 && cmp(p[x],p[k])) x=k;
}
point y=p[x];
for (k=l;k<=r;k++){
s[++i]=cross(p[k],a,y);
if (sgn(s[i])>0) swap(p[i],p[k]); else i--;
}
for (k=r;k>=l;k--){
s[--j]=cross(p[k],y,b);
if (sgn(s[j])>0) swap(p[j],p[k]); else j++;
}
if (l<=i) hull(l,i,a,y);
set[++tot]=y;
if (j<=r) hull(j,r,y,b);
}
void solve(double &ans){
double tmp;
int i=1,j=2,k=3;
set[tot+1]=set[1];
while(k!=1){
int ii=i,jj=j,kk=k;
while((tmp=cross(set[i],set[k],set[j]))<cross(set[i],set[k+1],set[j])){
k++; if(k>tot) k=1;
}ans=max(ans,tmp);
while((tmp=cross(set[i],set[k],set[j]))<cross(set[i],set[k],set[j+1])){
j++; if(j>tot) j=j;
} ans=max(ans,tmp);
while((tmp=cross(set[i],set[k],set[j]))<cross(set[i+1],set[k],set[j])){
i++; if(i>tot) i=1;
}ans=max(ans,tmp);
if(ii==i&&jj==j&&kk==k) k=(k+1)%tot;
}
ans/=2;
}
int main(){
int n,i,j,x=0;
while(scanf("%d",&n),n!=-1){
tot=1;
for (i=1;i<=n;i++){
scanf("%lf %lf",&p[i].x,&p[i].y);
if (x==0 || cmp(p[i],p[x])) x=i;
}
swap(p[1],p[x]);
set[1]=p[1];
hull(2,n,p[1],p[1]);
double ans=0;
solve(ans);
printf("%.2lf\n",ans);
}
return 0;
}
最远点对肯定在凸包的顶点上
View Code
//快速土包算法，递归
#include <iostream>
#include <math.h>
#include <cstdio>
#include<algorithm>
#define maxn 100000
#define zero 1e-8
#define max(x,y) x>y?x:y
#define sgn(x) (fabs(x)<zero?0:(x>0?1:-1))
#define cross(a,b,c) ((b.x-a.x)*(c.y-a.y)-(b.y-a.y)*(c.x-a.x))
#define cmp(a,b) (a.x<b.x || sgn(a.x-b.x)==0 && a.y<b.y)
using namespace std;
struct point{
double x,y;
}p[maxn],convex_set[maxn];
double s[maxn];
int tot=1;
void hull(int l,int r,point a,point b){
int x=l,i=l-1,j=r+1,k;
for (k=l;k<=r;k++){
double temp=sgn(s[x]-s[k]);
if (temp<0 || temp==0 && cmp(p[x],p[k])) x=k;//找距离最远点
}
point y=p[x];
for (k=l;k<=r;k++){
s[++i]=cross(p[k],a,y);
if (sgn(s[i])>0) swap(p[i],p[k]); else i--;//划分点集
}
for (k=r;k>=l;k--){
s[--j]=cross(p[k],y,b);
if (sgn(s[j])>0) swap(p[j],p[k]); else j++;//划分点集
}
if (l<=i) hull(l,i,a,y);
convex_set[++tot]=y;
if (j<=r) hull(j,r,y,b);
}
double dist(point a,point b)
{
return ((a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y));
}
void solve(double &ans)
{
int i,j=2;
convex_set[tot+1]=convex_set[1];
for(i=1;i<=tot;i++)
{
while(cross(convex_set[i],convex_set[j],convex_set[i+1])<cross(convex_set[i],convex_set[j+1],convex_set[i+1]))
{
j++;
if(j>tot) j=1;
}
ans=max(ans,dist(convex_set[j],convex_set[i]));
}
}
int main(){
int n,i,j,x=0;
scanf("%d",&n);
for (i=1;i<=n;i++){
scanf("%lf %lf",&p[i].x,&p[i].y);
if (x==0 || cmp(p[i],p[x])) x=i;
}
swap(p[1],p[x]);
convex_set[1]=p[1];
hull(2,n,p[1],p[1]);
double ans=0;
solve(ans);
printf("%.0lf\n",ans);
return 0;
}