旋转卡壳模板
注意本题要输入输出的都是整数，我一般的计算几何模板都是double，用%d输入到double里得到的都是0！
#include<bits/stdc++.h>
using namespace std;
const int N = 50007, M = 50007, INF = 0x3f3f3f3f;
const double DINF = 12345678910, eps = 1e-10, PI = acos(-1);
struct Point{
int x, y;Point(double x = 0, double y = 0):x(x), y(y){
}//构造函数
};
typedef Point Vector;
Vector operator + (Vector A, Vector B){
return Vector(A.x + B.x, A.y + B.y);}
Vector operator - (Point A, Point B){
return Vector(A.x - B.x, A.y - B.y);}
Vector operator * (Vector A, double p){
return Vector(A.x * p, A.y * p);}
Vector operator / (Vector A, double p){
return Vector(A.x / p, A.y / p);}
bool operator < (const Point& a, Point& b) {
return a.x < b.x || (a.x == b.x && a.y < b. y);}
int dcmp(double x){
if(fabs(x) < eps) return 0;else return x < 0 ? -1 : 1;
}
bool operator == (const Point& a, const Point& b){
return !dcmp(a.x - b.x) && !dcmp(a.y - b.y);}
double Polar_angle(Vector A){
return atan2(A.y, A.x);}
inline double D_to_R(double D)//角度转弧度
{
return PI/180*D; }
double Cross(Vector A, Vector B){
return A.x * B.y - B.x * A.y;}
Vector Rotate(Vector A, double rad){
return Vector(A.x * cos(rad) - A.y * sin(rad), A.x * sin(rad) + A.y * cos(rad));
}
Point Get_line_intersection(Point P,Vector v,Point Q,Vector w)
{
Vector u = P - Q;double t = Cross(w, u) / Cross(v, w);return P + v * t;
}
double convex_polygon_area(Point* p, int n)
{
double area = 0;for(int i = 1; i <= n - 2; ++ i)area += Cross(p[i] - p[0], p[i + 1] - p[0]);return area / 2;
}
int ConvexHull(Point* p, int n, Point* ch)
{
sort(p, p + n);int m = 0;for(int i = 0; i < n; ++ i){
//下凸包while(m > 1 && Cross(ch[m - 1] - ch[m - 2], p[i] - ch[m - 2]) <= 0)m -- ;ch[m ++ ] = p[i];}int k = m;for(int i = n - 2; i >= 0; -- i){
//上凸包while(m > k && Cross(ch[m - 1] - ch[m - 2], p[i] - ch[m - 2]) <= 0)m -- ;ch[m ++ ] = p[i];}if(n > 1) m -- ;return m;
}
int get_dist (const Point &x){
return x.x * x.x + x.y * x.y;}
Point p[N], con[N];
int con_num;
double Rotating_calipers()
{
int op = 1, ans = 0;for(int i = 0; i < con_num; ++ i){
while(Cross((con[i] - con[op]), (con[i + 1] - con[i])) < Cross((con[i] - con[op + 1]), (con[i + 1] - con[i])))op = (op + 1) % con_num;ans = max(ans, max(get_dist(con[i] - con[op]), get_dist(con[i + 1] - con[op])));}printf("%d\n", ans);return ans;
}
int n ;
int main()
{
scanf("%d", &n);for(int i = 0; i < n; ++ i){
scanf("%d%d", &p[i].x, &p[i].y);}con_num = ConvexHull(p, n, con);double res = Rotating_calipers();return 0;
}