本文主要是介绍POJ 2187 Beauty Contest (凸包最远点距旋转卡壳)，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
http://poj.org/problem?id=2187
思路：算出凸包后枚举凸包上的点。复杂度为O(NlogN+M)
为什么可以枚举？
设坐标的绝对值不超过M，则凸包至多有O(√M)个顶点
证明：以(0,0)为起点画出如下“极限凸包”
(0,0)-(1,0)-(2,1)-(3,3)-(4,6)-...当x每次只增加1时，y增加速率是平方级的，所以凸包至多有O(√M)个顶点。
另一种思路就是用旋转卡壳(RC)算法。复杂度为O(NlogN+√M)
枚举算法的代码：
/*79ms,956KB*/#include<cstdio>
#include<algorithm>
using namespace std;
const int mx = 50005;struct P
{int x, y;P(int x = 0, int y = 0): x(x), y(y) {}void read(){scanf("%d%d", &x, &y);}P operator - (P& p){return P(x - p.x, y - p.y);}bool operator < (const P& p) const///加cosnt以便sort调用，其他函数不加const对速度没有影响{return x < p.x || x == p.x && y < p.y;}int dot(P p){return x * p.x + y * p.y;}int det(P p){return x * p.y - y * p.x;}
};P p[mx], ans[mx];
int n, len;///求凸包
void convex_hull()
{sort(p, p + n);len = 0;int i;for (i = 0; i < n; ++i){while (len >= 2 && (ans[len - 1] - ans[len - 2]).det(p[i] - ans[len - 1]) <= 0)--len;ans[len++] = p[i];}int tmp = len;for (i = n - 2; i >= 0; --i){while (len > tmp && (ans[len - 1] - ans[len - 2]).det(p[i] - ans[len - 1]) <= 0)--len;ans[len++] = p[i];}--len;
}int main()
{int i, j;scanf("%d", &n);for (i = 0; i < n; ++i) p[i].read();convex_hull();int mxdis = 0;for (i = 1; i < len; ++i)for (j = 0; j < i; ++j)mxdis = max(mxdis, (ans[i] - ans[j]).dot(ans[i] - ans[j]));printf("%d\n", mxdis);return 0;
}
旋转卡壳算法的代码：（速度差不多，看来是排序占用了大量时间）
/*79ms,956KB*/#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int mx = 50005;struct P
{int x, y;P(int x = 0, int y = 0): x(x), y(y) {}void read(){scanf("%d%d", &x, &y);}P operator - (P p){return P(x - p.x, y - p.y);}bool operator < (const P& p) const{return x < p.x || x == p.x && y < p.y;}int dot(P p){return x * p.x + y * p.y;}int det(P p){return x * p.y - y * p.x;}
};P p[mx], ans[mx];
int n, len;///求凸包
void convex_hull()
{sort(p, p + n);len = 0;int i;for (i = 0; i < n; ++i){while (len >= 2 && (ans[len - 1] - ans[len - 2]).det(p[i] - ans[len - 1]) <= 0)--len;ans[len++] = p[i];}int tmp = len;for (i = n - 2; i >= 0; --i){while (len > tmp && (ans[len - 1] - ans[len - 2]).det(p[i] - ans[len - 1]) <= 0)--len;ans[len++] = p[i];}--len;memcpy(p, ans, sizeof(P) * len);
}inline int next(int i)
{return (i + 1) % len;
}int RC(int si, int sj)
{int mxdis = 0, i = si, j = sj;while (i != sj || j != si){mxdis = max(mxdis, (p[i] - p[j]).dot(p[i] - p[j]));if ((p[next(i)] - p[i]).det(p[next(j)] - p[j]) > 0) j = next(j);else i = next(i);}return mxdis;
}int main()
{int i, si = 0, sj = 0;scanf("%d", &n);for (i = 0; i < n; ++i) p[i].read();convex_hull();if (len == 2) printf("%d\n", (p[0] - p[1]).dot(p[0] - p[1]));else{for (i = 0; i < len; ++i){if (!(p[si] < p[i])) si = i;if (p[sj] < p[i]) sj = i;}printf("%d\n", RC(si, sj));}return 0;
}
这篇关于POJ 2187 Beauty Contest (凸包最远点距旋转卡壳)的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
