http://poj.org/problem?id=2187
题意 ：有一个农场有N个房子，问最远的房子相距多少距离 。
思路 ：凸包，旋转卡壳，通过寻找所有的对锺点，找出最远的点对。
#include <iostream> #include <stdio.h> #include <string.h> #include <stdlib.h> #include <algorithm> using namespace std ; typedef long long ll ; const int maxn = 50000 ; struct point { int x ; int y ; }p[maxn],ch[maxn] ; int det(int x1,int y1,int x2,int y2 )//叉积 { return x1*y2-x2*y1 ; } int side(point a,point b,point p)//两个向量的叉积，平行四边形面积 { return det(b.x-a.x,b.y-a.y,p.x-a.x,p.y-a.y) ; } int squre_dis(point a,point b)//两点之间的距离 { return (a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y) ; } bool cmp(point a,point b) { if(a.y == b.y) return a.x < b.x ; return a.y < b.y ; } int convex_hull(point p[],int n)//凸包 { sort(p,p+n,cmp) ; ch[0] = p[0] ; if(n == 1) {ch[1] = ch[0] ;return 1 ;} ch[1] = p[1] ; if(n == 2) {ch[2] = ch[0] ;return 2 ;} int ix = 2 ; for(int i = 2 ; i < n ; i++) { while(ix > 1&&side(ch[ix-2],ch[ix-1],p[i] )<= 0) --ix ; ch[ix++] = p[i] ; } int t = ix ; ch[ix++] = p[n-2] ; for(int i = n-3 ; i >= 0 ; i--) { while(ix > t && side(ch[ix-2],ch[ix-1],p[i]) <= 0) --ix ; ch[ix++] = p[i] ; } return ix-1 ; } //int dia_numerator(int cn) //{ // int dia = 0; // for(int i = 0 ; i < cn ; i++) // { // for(int j = 0 ; i < cn ; j++) // { // int t = squre_dis(ch[i],ch[j]) ; // dia = t > dia ? t : dia ; // } // } // return dia ; //} int dia_rotating_calipers(int n)//旋转卡壳 { int dia = 0 ; int q = 1 ; for(int i = 0 ; i < n ; i++) { while(side(ch[i],ch[i+1],ch[q+1]) > side(ch[i],ch[i+1],ch[q])) q = (q+1)%n ; dia = max(dia,max(squre_dis(ch[i],ch[q]),squre_dis(ch[i+1],ch[q+1]))) ; } return dia ; } int main() { int n,cn ; scanf("%d",&n) ; for(int i = 0 ; i < n ; i++) scanf("%d %d",&p[i].x,&p[i].y) ; cn = convex_hull(p,n) ; printf("%d ",dia_rotating_calipers(cn)) ; return 0 ; }