POJ2079 Triangle

题面

题解

我什么时候会过这种东西？？？（逃

旋转卡壳板子题（听说这个算法有十六种读音？？？

我是真的忘了这道题目怎么做了，挂个(blog)，等我学会了再写题解

我的代码里居然有注释？？？好像还是蒯的上面那个博客的

运算符之间没有空格？居然using namespace std？？？果然是上古代码

本来我还想用模拟退火过的。。。

代码

好丑，凑合着看吧。。。

#include<iostream>
#include<cmath>
#include<algorithm>
#include<ctime>
#define RG register
#define clear(x, y) memset(x, y, sizeof(x));
using namespace std;

const int maxn(50010);
inline double sqr(const double &x) { return x*x; }
struct point
{
	double x, y;
	point() {}
	point(double dx, double dy) : x(dx), y(dy) {}
	inline void read() { scanf("%lf%lf", &x, &y); }
	inline bool operator < (const point &rhs) const
	{
		return x<rhs.x || (x==rhs.x && y<rhs.y);
	}

	inline point operator - (const point &rhs)
	{
		return point(x-rhs.x, y-rhs.y);
	}

	inline double operator * (const point &rhs)
	{
		return x*rhs.y-rhs.x*y;
	}
}p[maxn];

int n, stk[maxn], top;
inline double dis(point a, point b) { return sqrt(sqr(a.x - b.x) + sqr(a.y - b.y)); }
inline bool goleft(point a, point b, point c)
{
	double s((b-a)*(c-a));
	return s<0 || (s==0 && dis(a, b) >= dis(a, c));
}

inline double area(point a, point b, point c) { return abs((b-a) * (c-a) * 0.5); }
inline bool cmp(const point &a, const point &b) { return goleft(p[1], a, b); }

inline double rotating_calipers()
{
	int a = 1, b = 2;
	double ans = 0;
	p[stk[0]] = p[stk[top]];
	for(RG int i=0;i<top;i++)
	{
		while(area(p[stk[i]], p[stk[a]], p[stk[b + 1]]) > area(p[stk[i]], p[stk[a]], p[stk[b]])) b = (b + 1) % top; // 定点i, a, b,先i,a固定,让b旋转找到最大的面积三角形,还是利用了凸包的单峰函数
		ans = max(ans, area(p[stk[i]], p[stk[a]], p[stk[b]]));
		while(area(p[stk[i]], p[stk[a + 1]], p[stk[b]]) > area(p[stk[i]], p[stk[a]], p[stk[b]])) a = (a + 1) % top; // i, a固定, b旋转, 找到最大的三角形面积, 比较记录.
		ans = max(ans, area(p[stk[i]], p[stk[a]], p[stk[b]]));
	}
	return ans;
}

int main()
{
	while(~scanf("%d", &n) && ~n)
	{
		for(RG int i=1;i<=n;i++) p[i].read();
		int first=1;
		for(RG int i=2;i<=n;i++) if(p[i]<p[first]) first=i;
		swap(p[1], p[first]);
		sort(p+2, p+n+1, cmp);
		p[n+1]=p[1]; stk[1]=1; stk[top=2]=2;
		for(RG int i=3;i<=n+1;i++)
		{
			while(top>1 && goleft(p[stk[top-1]], p[i], p[stk[top]])) --top;
			stk[++top]=i;
		}
		top--; printf("%.2lf
", rotating_calipers());
	}
	return 0;
}