//Place your snippets for cpp here. Each snippet is defined under a snippet name and has a prefix, body and 
// description. The prefix is what is used to trigger the snippet and the body will be expanded and inserted. Possible variables are:
// $1, $2 for tab stops, $0 for the final cursor position, and ${1:label}, ${2:another} for placeholders. Placeholders with the 
// same ids are connected.
// prefix 的格式要求是 acm-[一级标题编号].[二级标题编号][该代码片段的英文简称]
// description 的格式要求是 "插入 [该代码片段的中文名]"

{
    "求凸包直径（旋转卡壳）": {
        "prefix": "acm-8.3tubao",
        "body": [
            "#include <bits/stdc++.h>",
            "#include <ext/pb_ds/assoc_container.hpp> // 包含所有容器（哈希表、树、堆）",
            "#include <ext/pb_ds/tree_policy.hpp>     // 包含树的相关策略（用于实现平衡树）",
            "#include <ext/pb_ds/hash_policy.hpp>     // 包含哈希表的相关策略",
            "//#include <ext/pb_ds/priority_queue.hpp>  // 包含优先级队列（堆）",
            "using namespace std;",
            "using namespace __gnu_pbds;",
            "using ll = long long;",
            "template <typename T> using ordered_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;",
            "#define up(i, a, b) for (int i = (a); i <= (b); ++i)",
            "#define down(i, a, b) for (int i = (a); i >= (b); --i)",
            "#define sm int,vector<int>,greater<int>",
            "#define int long long",
            "mt19937_64 gen(12345);",
            "const int N=1e6+5,mod=998244353,inf=1e9+7;;",
            "int n,m,q,k;",
            "int a[N],b[N],c[N],d[N];",
            "int gcd(int x,int y)",
            "{",
            "\tif(y==0)return x;",
            "\treturn gcd(y,x%y);",
            "}",
            "int ksm(int a,int n,int p)",
            "{",
            "\tif(n<0)return 0;",
            "\tint res=1;",
            "\twhile(n)",
            "\t{",
            "\t\tif(n&1)res=res*a%p;",
            "\t\tn>>=1;",
            "\t\ta=a*a%p;",
            "\t}",
            "\treturn res;",
            "}",
            "const double eps = 1e-9;",
            "int sgn(double x) {",
            "\tif (abs(x) < eps) return 0;",
            "\treturn x < 0 ? -1 : 1;",
            "}",
            "struct Point {",
            "\tdouble x, y;",
            "\tPoint(double _x = 0, double _y = 0) : x(_x), y(_y) {}",
            "\t",
            "\tPoint operator - (const Point& b) const {",
            "\t\treturn Point(x - b.x, y - b.y);",
            "\t}",
            "\t",
            "\t//优先按 x 排序，x 相同按 y 排序",
            "\tbool operator < (const Point& b) const {",
            "\t\tif (sgn(x - b.x) == 0) return sgn(y - b.y) < 0;",
            "\t\treturn sgn(x - b.x) < 0;",
            "\t}",
            "\t",
            "\t// 判等（用于去重）",
            "\tbool operator == (const Point& b) const {",
            "\t\treturn sgn(x - b.x) == 0 && sgn(y - b.y) == 0;",
            "\t}",
            "};",
            "",
            "double cross(const Point& a, const Point& b) {",
            "\treturn a.x * b.y - a.y * b.x;",
            "}",
            "",
            "// 返回值 > 0：p2 在 p0->p1 的左侧（向左转）",
            "// 返回值 < 0：p2 在 p0->p1 的右侧（向右转）",
            "// 返回值 == 0：三点共线",
            "double cross(const Point& p0, const Point& p1, const Point& p2) {",
            "\treturn cross(p1 - p0, p2 - p0);",
            "}",
            "",
            "int dist(const Point& p0, const Point& p1){",
            "\treturn (p0.x-p1.x)*(p0.x-p1.x)+(p0.y-p1.y)*(p0.y-p1.y);",
            "}",
            "// 输入点集 P，返回凸包上的点集（逆时针顺序，起点和终点不重合）",
            "vector<Point> convex_hull(vector<Point>& P) {",
            "\tint n = P.size();",
            "\tif (n <= 2) return P; // 退化情况：点数小于等于2，本身就是凸包",
            "\t",
            "\t// 1. 排序并去重",
            "\tsort(P.begin(), P.end());",
            "\tP.erase(unique(P.begin(), P.end()), P.end());",
            "\tn = P.size();",
            "\tif (n <= 2) return P;",
            "\t",
            "\tvector<Point> hull(2 * n); // 用数组模拟栈，速度最快",
            "\tint top = 0;               // 栈顶指针，表示栈内元素个数",
            "\t",
            "\t// 2. 求下凸壳",
            "\tfor (int i = 0; i < n; i++) {",
            "\t\t// 【核心判断】：如果向右转或共线，则弹栈",
            "\t\t// 注意：如果你需要保留凸包边上的共线点，把 <= 改成 < 即可",
            "\t\twhile (top >= 2 && sgn(cross(hull[top - 2], hull[top - 1], P[i])) <= 0) {",
            "\t\t\ttop--;",
            "\t\t}",
            "\t\thull[top++] = P[i];",
            "\t}",
            "\t",
            "\t// 3. 求上凸壳",
            "\tint tmp = top; // 记录下凸壳的元素个数，上凸壳弹栈时不能破坏下凸壳",
            "\tfor (int i = n - 2; i >= 0; i--) {",
            "\t\twhile (top > tmp && sgn(cross(hull[top - 2], hull[top - 1], P[i])) <= 0) {",
            "\t\t\ttop--;",
            "\t\t}",
            "\t\thull[top++] = P[i];",
            "\t}",
            "\t",
            "\tif (n > 1) top--;",
            "\thull.resize(top);",
            "\treturn hull;",
            "}",
            "int hull_diam(vector<Point>& hull){",
            "\tint j=2;",
            "\tint ans=0,H=hull.size();",
            "\tif (H == 2) {",
            "        return dist(hull[0], hull[1]) ;",
            "    }",
            "    if (H <= 1) {",
            "        return 0;",
            "    }",
            "\tup(i,0,H-1){",
            "\t\tint next_i=(i+1)%H;",
            "\t\twhile(cross(hull[i],hull[next_i],hull[j])<=cross(hull[i],hull[next_i],hull[(j+1)%H])){",
            "\t\t\tj=(j+1)%H;",
            "\t\t}",
            "\t\tans=max(ans,dist(hull[i],hull[j]));",
            "\t\tans=max(ans,dist(hull[next_i],hull[j]));",
            "\t}",
            "\treturn ans;   ",
            "}",
            "void solve(){",
            "\tcin>>n;",
            "\tvector<Point>pts(n);",
            "\tup(i,0,n-1)cin>>pts[i].x>>pts[i].y;",
            "\tvector<Point>hull=convex_hull(pts);",
            "\tcout<<hull_diam(hull);",
            "}",
            "",
            "signed main() ",
            "{",
            "\tios::sync_with_stdio(0);",
            "\tcin.tie(0), cout.tie(0);",
            "\tint t = 1;",
            "\t// cin >> t;",
            "\twhile (t--){",
            "\t\tsolve();",
            "\t}",
            "//\tsystem(\"x-www-browser https://ys.mihoyo.com/\");",
            "//\tcout << fixed << setprecision(10) << x << '\\n';",
            "\treturn 0;",
            "}",
            "/*",
            "1",
            "38133 49107",
            "",
            "2 27269",
            "",
            "",
            "*/"
        ],
        "description": "插入 求凸包直径（旋转卡壳）"
    }
}