http://poj.org/problem?id=2187
题意
给n个坐标，求最远点对的距离平方值。
分析
模板题，旋转卡壳求求两点间距离平方的最大值。
#include<iostream>
#include<cmath>
#include<cstring>
#include<queue>
#include<vector>
#include<cstdio>
#include<algorithm>
#include<map>
#include<set>
#define rep(i,e) for(int i=0;i<(e);i++)
#define rep1(i,e) for(int i=1;i<=(e);i++)
#define repx(i,x,e) for(int i=(x);i<=(e);i++)
#define X first
#define Y second
#define PB push_back
#define MP make_pair
#define mset(var,val) memset(var,val,sizeof(var))
#define scd(a) scanf("%d",&a)
#define scdd(a,b) scanf("%d%d",&a,&b)
#define scddd(a,b,c) scanf("%d%d%d",&a,&b,&c)
#define pd(a) printf("%d\n",a)
#define scl(a) scanf("%lld",&a)
#define scll(a,b) scanf("%lld%lld",&a,&b)
#define sclll(a,b,c) scanf("%lld%lld%lld",&a,&b,&c)
#define IOS ios::sync_with_stdio(false);cin.tie(0)
#define lc idx<<1
#define rc idx<<1|1
#define rson mid+1,r,rc
#define lson l,mid,lc
using namespace std;
typedef long long ll;
template <class T>
void test(T a) {
cout<<a<<endl;
}
template <class T,class T2>
void test(T a,T2 b) {
cout<<a<<" "<<b<<endl;
}
template <class T,class T2,class T3>
void test(T a,T2 b,T3 c) {
cout<<a<<" "<<b<<" "<<c<<endl;
}
const int inf = 0x3f3f3f3f;
const ll INF = 0x3f3f3f3f3f3f3f3fll;
const ll mod = 1e9+;
int T;
void testcase() {
printf("Case %d: ",++T);
}
const int MAXN = ;
const int MAXM = ;
const double PI = acos(-1.0);
const double eps = 1e-; struct Point{
int x,y;
Point(int _x=,int _y=){
x=_x,y=_y;
}
Point operator -(const Point &b)const{
return Point(x-b.x,y-b.y);
}
int operator ^(const Point &b)const{
return x*b.y-y*b.x;
}
int operator *(const Point &b)const{
return x*b.x+y*b.y;
}
void input(){
scanf("%d%d",&x,&y);
}
};
int dis2(Point a,Point b){
return (a-b)*(a-b);
}
Point List[MAXN];
int Stack[MAXN],top;
bool _cmp(Point p1,Point p2){
int tmp=(p1-List[])^(p2-List[]);
if(tmp>) return true;
else if(tmp==&&dis2(p1,List[])<=dis2(p2,List[])) return true;
else return false;
}
void Graham(int n){
Point p0;
int k=;
p0=List[];
for(int i=;i<n;i++){
if(p0.y>List[i].y||(p0.y==List[i].y&&p0.x>List[i].x)){
p0=List[i];
k=i;
}
}
swap(List[k],List[]);
sort(List+,List+n,_cmp);
if(n==){
top=;
Stack[]=;
return;
}
if(n==){
top=;
Stack[]=;
Stack[]=;
return;
}
Stack[]=;
Stack[]=;
top=;
for(int i=;i<n;i++){
while(top>&&((List[Stack[top-]]-List[Stack[top-]])^(List[i]-List[Stack[top-]]))<=)
top--;
Stack[top++]=i;
}
return;
}
int rotating_calipers(Point p[],int n){
int ans=;
Point v;
int cur=;
for(int i=;i<n;i++){
v=p[i]-p[(i+)%n];
while((v^(p[(cur+)%n]-p[cur]))<)
cur=(cur+)%n;
ans=max(ans,max(dis2(p[i],p[cur]),dis2(p[(i+)%n],p[(cur+)%n])));
}
return ans;
}
Point p[MAXN];
int main() {
#ifdef LOCAL
freopen("data.in","r",stdin);
#endif // LOCAL
int n;
while(~scanf("%d",&n)){
for(int i=;i<n;i++) List[i].input();
Graham(n);
for(int i=;i<top;i++) p[i]=List[Stack[i]];
printf("%d\n",rotating_calipers(p,top));
}
return ;
}