旋转卡壳模板
注意本题要输入输出的都是整数，我一般的计算几何模板都是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; }