// POJ 2187 Beauty Contest -- Andrew凸包算法 + 点对距离最长(旋转卡壳)
// 大意：给你一堆点，让你求出相隔最远的两点距离并输出
// 要求：最后结果不需要开平方 应为距离的平方
//
/*test data
5
1 3
2 1
4 1
5 3
3 5
== 17
*/
#include <cstdio>
#include <cmath>
#include <algorithm>
using namespace std;
const double Pzero =
0.000001;
const int MAXP =
50005;
struct Point
{
double x, y;
//点对应坐标
Point() {}
Point(double x,
double y):x(x), y(y) {}
//使用两点进行初始化
} p[MAXP],CHp[MAXP*
2];
typedef Point Vec;
template<
class T> inline T sqr(T x)
//求平方
{
return x *
x;
}
Vec operator - (Vec a, Vec b)
//点减法
{
return Vec(a.x - b.x, a.y -
b.y);
}
bool operator < (Point a, Point b)
//平面直角坐标系中左下方的为小
{
return a.x < b.x || (a.x == b.x && a.y <
b.y);
}
inline double crossDet(Vec a, Vec b)
//叉乘
{
return a.x * b.y - a.y *
b.x;
}
inline double crossDet(Point o, Point a, Point b)
//向量叉乘
{
return crossDet(a - o, b -
o);
}
int andrew(Point *pt,
int n, Point *
ch)
{
sort(pt, pt +
n);
int m =
0;
for(
int i =
0; i < n; i++
)
{
while(m >
1 && crossDet(ch[m -
1] - ch[m -
2], pt[i] - ch[m -
2]) <=
0) m--
;
ch[m++] =
pt[i];
}
int k =
m;
for(
int i = n -
2; i >=
0; i--
)
{
while(m > k && crossDet(ch[m -
1] - ch[m -
2], pt[i] - ch[m -
2]) <=
0) m--
;
ch[m++] =
pt[i];
}
if(n >
1) m--
;
return m;
}
inline double unsqrtptDis(Point a, Point b)
//内敛点间距
{
return sqr(a.x - b.x) + sqr(a.y -
b.y);
}
double rotating_calipers(Point *ch,
int n){
// 旋转卡壳 求点对最长距离 效率 O(n)
// ch[] 凸包 为逆时针给出的
// 计算最长距离的时候，枚举了每一条边 |p p+1| 及 离该边最远的点q 的情况， 每一次计算点到边两端的距离，并更新一下ans（取最大值）
// 如果遇到下一个点与该线段围成的三角形面积(即叉积) 比这一次变大了，则比较下一个点 （即q++）
// 如果遇到下一个点与该线段围成的三角形面积(即叉积) 比这一次变小了，则计算两个距离（因为会出现平行的情况）并更新ans
// POJ 2187 暴力可过 肯定凸包的顶点数不多
int q =
1;
double ans =
0;
ch[n] = ch[
0];
// ch[q+1] 可能会访问到
for(
int p =
0; p <n; p++
){
// 此处遍历的线段为 |p->p+1| 点为 q
// 所以叉积的意义为 线段|p->p+1| 和 点q 围成的三角形的有向面积，逆时针为正，因此在这里均为正
while(crossDet(ch[p+
1], ch[q], ch[p]) < crossDet(ch[p+
1], ch[q+
1], ch[p]))
q = (q +
1) % n;
// 移到下一个点，因为q可能会转几圈，因此对n取余
// 这里要比较q点到线段 |p->p+1| 两个端点的距离，因为有可能在旋转的时候两个边平行
ans = max( ans, max(unsqrtptDis(ch[p], ch[q]), unsqrtptDis(ch[p+
1], ch[q+
1])) );
}
return ans;
}
void InitInput(
int n){
for(
int i=
0;i<n;i++
){
scanf("%lf%lf", &p[i].x, &
p[i].y);
}
}
int main()
{
// freopen("in.txt","r",stdin);
// freopen("C:\\Users\\Sky\\Desktop\\1.in","r",stdin);
int n;
while( ~scanf(
"%d",&
n) ){
InitInput(n);
int nCHp = andrew(p,n,CHp);
// 返回凸包的顶点数
//reverse(&CHp[0],&CHp[nCHp+1]);
// for(int i=0;i<=nCHp;i++)
// {
// printf("%.0lf %.0lf\n",CHp[i].x,CHp[i].y);
// }
printf(
"%.0lf\n", rotating_calipers(CHp, nCHp) );
}
return 0;
}
View Code
Beauty Contest
Time Limit: 3000MS Memory Limit: 65536KTotal Submissions: 25095 Accepted: 7702
Description
Bessie, Farmer John's prize cow, has just won first place in a bovine beauty contest, earning the title 'Miss Cow World'. As a result, Bessie will make a tour of N (2 <= N <= 50,000) farms around the world in order to spread goodwill between farmers and their cows. For simplicity, the world will be represented as a two-dimensional plane, where each farm is located at a pair of integer coordinates (x,y), each having a value in the range -10,000 ... 10,000. No two farms share the same pair of coordinates.
Even though Bessie travels directly in a straight line between pairs of farms, the distance between some farms can be quite large, so she wants to bring a suitcase full of hay with her so she has enough food to eat on each leg of her journey. Since Bessie refills her suitcase at every farm she visits, she wants to determine the maximum possible distance she might need to travel so she knows the size of suitcase she must bring.Help Bessie by computing the maximum distance among all pairs of farms.
Input
* Line 1: A single integer, N
* Lines 2..N+1: Two space-separated integers x and y specifying coordinate of each farm
Output
* Line 1: A single integer that is the squared distance between the pair of farms that are farthest apart from each other.
Sample Input
4
0 0
0 1
1 1
1 0
Sample Output
2
Hint
Farm 1 (0, 0) and farm 3 (1, 1) have the longest distance (square root of 2)
转载于:https://www.cnblogs.com/Skyxj/p/3351839.html
