●POJ 2079 Triangle

题链：

http://poj.org/problem?id=2079

题解：

计算几何，凸包，旋转卡壳

复杂度O（N^2），（O（N）什么的就不说了，我觉得我看过的O（N）方法正确性都有问题，虽然有些AC了，那应该是鲁棒性太强了，谁叫他们非要每挪动一步都取MAX的呢）

做法：

（三角形的三个顶点在凸包的顶点上，同时显然三角形的底边不一定为凸包的边啦！）

枚举i，j两点，使得有向线段$\vec{ij}$作为三角形底边。

然后在有向线段$\vec{ij}$的右侧区域（凸包上），寻找k点使得三角形ijk面积最大，用叉积判断是第k个点优还是第k+1个点优。

注意到单调性，k可以用旋转卡壳的思想枚举得到。

附一个简单的证明：三角形的顶点一定在凸包顶点上：

假设现在取得一个三角形P1P2P3,且P1在凸包内。

做过P1的直线l垂直于线段P2P3所在的直线。

显然，把P1点沿着垂线l，向远离线段P2P3的方向移动会使得三角形面积增大。

最后会移动到凸包的顶点上或者凸包的一条边上。

若移到了顶点上，那就表明三角形的定点在凸包的顶点上最优。

若在移到了凸包的一条边上，那也可以通过在边上移动直到达到一个顶点，这样也会使面积变大。

综上，三角形的三个顶点一定在凸包的定点上。

代码：

#include<cmath>

#include<cstdio>

#include<cstring>

#include<iostream>

#include<algorithm>

#define MAXN 50050

using namespace std;

const double eps=1e-8;

int sign(double x){

	if(fabs(x)<=eps) return 0;

	return x<0?-1:1;

}

struct Point{

	double x,y;

	Point(double _x=0,double _y=0):x(_x),y(_y){}

	void Read(){scanf("%lf%lf",&x,&y);}

};

typedef Point Vector;

bool operator < (Point A,Point B){return sign(A.x-B.x)<0||(sign(A.x-B.x)==0&&sign(A.y-B.y)<0);}

bool operator == (Point A,Point B){return sign(A.x-B.x)==0&&sign(A.y-B.y)==0;}

Vector operator - (Point A,Point B){return Vector(A.x-B.x,A.y-B.y);}

double operator ^ (Vector A,Vector B){return A.x*B.y-A.y*B.x;}

double operator * (Vector A,Vector B){return A.x*B.x+A.y*B.y;}

Point D[MAXN],C[MAXN];

int Andrew(int dnt){

	int cnt=0,k;

	sort(D+1,D+dnt+1);

	dnt=unique(D+1,D+dnt+1)-D-1;

	for(int i=1;i<=dnt;i++){

		while(cnt>1&&sign((C[cnt]-C[cnt-1])^(D[i]-C[cnt-1]))<=0) cnt--;

		C[++cnt]=D[i];

	} k=cnt;

	for(int i=dnt-1;i>=1;i--){

		while(cnt>k&&sign((C[cnt]-C[cnt-1])^(D[i]-C[cnt-1]))<=0) cnt--;

		C[++cnt]=D[i];

	} if(dnt>1) cnt--;

	return cnt;

}

double DA(Point P,Point P1,Point P2){//Directd_Area

	return fabs((P1-P)^(P2-P));

}

double RC(int cnt){//Rotating_Calipers

	double S=0;

	if(cnt==1||cnt==2) return 0;

	C[cnt+1]=C[1];

	for(int i=1;i<=cnt;i++){

		int k=i+1;

		for(int cj=2,j;j=(i+cj-1)%cnt+1,cj<cnt;cj++){

			while(sign(DA(C[i],C[j],C[k])-DA(C[i],C[j],C[k+1]))<=0)

				k=k%cnt+1;

			S=max(S,DA(C[i],C[j],C[k]));

		}

	}

	return S/2;

}

int main(){

	int n;

	while(~scanf("%d",&n)&&n!=-1){

		for(int i=1;i<=n;i++) D[i].Read();

		printf("%.2lf\n",RC(Andrew(n)));

	}

	return 0;

}

巴特西

●POJ 2079 Triangle

最新文章

热门文章