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;
}

hdu 2202 最大三角形_凸包模板,布布扣,bubuko.com

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

原文：http://blog.csdn.net/neng18/article/details/22487297