hdu 2202 最大三角形_凸包模板

题意:略

思路:直接套用凸包模板

#include <iostream>
#include <cstdio>
#include <cmath>
#include <algorithm>
using namespace std;
#define N 50010
struct node{
int x,y,d;
}p[N];
int dist(node a,node b){
return (a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y);
}
int crossproduct(node a,node b,node c){
return (b.x-a.x)*(c.y-a.y)-(c.x-a.x)*(b.y-a.y);
}
bool cmp1(node a,node b){
return (a.x==b.x)?(a.y<b.y):(a.x<b.x);
}
bool cmp2(node a,node b){
int cp=crossproduct(p[0],a,b);
if(!cp)
return a.d<b.d;
return cp>0;
}
double Graham(int n){
int i,j,k;
sort(p,p+n,cmp1);
for(i=1;i<n;i++)
p[i].d=dist(p[0],p[i]);
sort(p+1,p+n,cmp2);
int top=1;
for(i=2;i<n;i++){
while(top>0&&crossproduct(p[i],p[top-1],p[top])<=0)
--top;
p[++top]=p[i];
}
p[++top]=p[0];
int R=1,D=0;
/*
for(int L=0;L<top;++L){
while(crossproduct(p[L],p[L+1],p[R])<crossproduct(p[L],p[L+1],p[R+1]))
R=(R+1)%top;
D=max(D,max(dist(p[L],p[R]),dist(p[L+1],p[R+1])));
}
*/
double sum=0;
for(i=0;i<top;i++)
for(j=i+1;j<top;j++)
for(k=j+1;k<top;k++)
if(sum<crossproduct(p[i],p[j],p[k]))
sum=crossproduct(p[i],p[j],p[k]);
return sum*0.5;
}
int main(int argc, char** argv) {
int n;
while(scanf("%d",&n)!=EOF){
for(int i=0;i<n;i++)
scanf("%d%d",&p[i].x,&p[i].y);
printf("%.2lf\n",Graham(n));
}
return 0;
}
上一篇:js省市区三级联动 升级版


下一篇:web简单连接html文件测试