本文共 1713 字，大约阅读时间需要 5 分钟。
给n个坐标，求最远点对的距离平方值。
模板题，旋转卡壳求求两点间距离平方的最大值。
#include #include #include #include #include #include #include #include #include #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,lcusing namespace std;typedef long long ll;template void test(T a) { cout< < void test(T a,T2 b) { cout< <<" "<< void test(T a,T2 b,T3 c) { cout< <<" "<<<" "< < 0) return true; else if(tmp==0&&dis2(p1,List[0])<=dis2(p2,List[0])) return true; else return false;}void Graham(int n){ Point p0; int k=0; p0=List[0]; for(int i=1;i List[i].y||(p0.y==List[i].y&&p0.x>List[i].x)){ p0=List[i]; k=i; } } swap(List[k],List[0]); sort(List+1,List+n,_cmp); if(n==1){ top=1; Stack[0]=0; return; } if(n==2){ top=2; Stack[0]=0; Stack[1]=1; return; } Stack[0]=0; Stack[1]=1; top=2; for(int i=2;i 1&&((List[Stack[top-1]]-List[Stack[top-2]])^(List[i]-List[Stack[top-2]]))<=0) top--; Stack[top++]=i; } return;}int rotating_calipers(Point p[],int n){ int ans=0; Point v; int cur=1; for(int i=0;i
转载于:https://www.cnblogs.com/fht-litost/p/9350036.html