Geometry

Point

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
const long double eps = 1e-9;

struct point {
    long double x;
    long double y;

    point(long double _x = 0, long double _y = 0){
        x = _x;
        y = _y;
    }

    long double square_length() const {
        return x * x + y * y;
    }
    //模长
    long double length() const {
        return sqrtl(x * x + y * y);
    }

    friend point operator+(const point& lp, const point& rp){
        return point(lp.x + rp.x, lp.y + rp.y);
    }

    friend point operator-(const point& lp, const point& rp){
        return point(lp.x - rp.x, lp.y - rp.y);
    }

    friend point operator*(const point& p, const long double& k){
        return point(p.x * k, p.y * k);
    }

    friend point operator*(const long double& k, const point& p){
        return point(p.x * k, p.y * k);
    }

    friend point operator/(const point& p, const long double& k){
        return point(p.x / k, p.y / k);
    }

    friend bool operator==(const point& lp, const point& rp){
        return abs(lp.x - rp.x) < eps && abs(lp.y - rp.y) < eps;
    }

    friend bool operator!=(const point& lp, const point& rp){
        return abs(lp.x - rp.x) > eps || abs(lp.y - rp.y) > eps;
    }
};

Dot & cross

1
2
3
4
5
6
7
8
9
//点乘
long double dot(const point& lp, const point& rp){
    return lp.x * rp.x + lp.y * rp.y;
}

//叉乘
long double cross(const point& lp, const point& rp){
    return lp.x * rp.y - lp.y * rp.x;
}

Distance

1
2
3
4
5
6
7
8
long double square_distance(const point& lp, const point& rp){
    return (lp.x - rp.x) * (lp.x - rp.x) + (lp.y - rp.y) * (lp.y - rp.y);
}   

//两点距离
long double distance(const point& lp, const point& rp){
    return sqrtl((lp.x - rp.x) * (lp.x - rp.x) + (lp.y - rp.y) * (lp.y - rp.y));
}

Rotate

1
2
3
4
5
6
7
8
const long double PI = 3.141592653589793;

//矢量旋转 逆时针旋转 o (弧度制)
point rotate(const point& v, long double o){
    long double x = v.x * cos(o) - v.y * sin(o);
    long double y = v.x * sin(o) + v.y * cos(o);
    return point(x, y);
}

Sin & cos & angle & polar_angle

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
//cos
long double cos(const point& lp, const point& rp){
    return dot(lp, rp) / lp.length() / rp.length();
}

//sin
long double sin(const point& lp, const point& rp){
    return cross(lp, rp) / lp.length() / rp.length();
}

//angle
long double angle(const point& lp, const point& rp){
    return acos(cos(lp, rp));
}

//极角 三 < 四 < 一 < 二 (象限)
long double polar_angle(const point& p){
    return atan2(p.y, p.x);
}

Point and line

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
//点到直线的距离 p到lp--rp的距离
long double distance(const point& lp, const point& rp, const point& p){
    point vl = rp - lp;
    point vr = p - lp;
    return cross(vl, vr) / vl.length();
}

//求垂点 p到直线lp--rp的垂点
point foot(const point& lp, const point& rp, const point& p){
    point vl = rp - lp;
    point vr = p - lp;
    long double k = dot(vl, vr) / vl.length() / vl.length();
    return lp + vl * k;
}

//点 p 是否在直线 lp-rp 上
bool on_line(const point& lp, const point& rp, const point& p) {
    point vl = rp - lp;
    point vr = p - lp;
    return sign(cross(vl, vr)) == 0;
}

//点 p 是否射线 lp->rp 上
bool on_ray(const point& lp, const point& rp, const point& p) {
    point vl = rp - lp;
    point vr = p - lp;
    return sign(cross(vl, vr)) == 0 && sign(dot(vl, vr)) != -1;
}

Line and line

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
//两直线交点
point intersect(const point& flp, const point& frp, const point& slp, const point& srp){
    point sf = flp - slp;
    point vf = frp - flp;
    point vs = srp - slp;
    long double k = cross(sf, vs) / cross(vs, vf);
    return flp + vf * k;
}

// 两直线是否平行 (直线的两点不能相同) / 需要考虑直线重合的情况
bool parallel(const point& flp, const point& frp, const point& slp, const point& srp) {
    point vf = frp - flp;
    point vs = srp - slp;
    return sign(cross(vs, vf)) == 0;
}

// 直线是否重合
bool equal(const point& flp, const point& frp, const point& slp, const point& srp) {
    point vf = frp - flp;
    point vs = srp - slp;
    point sf = flp - slp;
    return sign(cross(vs, vf)) == 0 && sign(cross(sf, vs)) == 0;
}

Point and segment

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
//符号判断
int sign(long double x){
    if(x > eps){//正数
        return 1;
    }
    if(x < -eps){//负数
        return -1;
    }
    return 0;
}

//点在线段上(含端点) lp rp 为线段端点
bool on_segment(const point& lp, const point& rp, const point& p){
    point vl = rp - lp;
    point vr = p - lp;
    long double sv = cross(vl, vr);
    if(sign(sv) != 0){//不在直线上
        return false;
    }
    long double cv = dot(vl, vr);
    if(sign(cv) == -1){//在线段外
        return false;
    }
    return vr.length() <= vl.length();
}

//点在线段上(不含端点) lp rp 为线段端点
bool on_segment_strict(const point& lp, const point& rp, const point& p){
    return on_segment(lp, rp, p) && lp != p && rp != p;
}

Circle

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
struct circle {
    point o;
    long double r;
};

//垂直平分线 两点式
pair<point, point> perpendicular(const point& lp, const point& rp){
    return { (lp + rp) / 2, (lp + rp) / 2 + rotate(rp - lp, PI / 2) };
}

//三点确定圆 (外接圆)
circle cover(const point& a, const point& b, const point& c){
    auto lp = perpendicular(a, b);
    auto rp = perpendicular(a, c);
    point o = intersect(lp.first, lp.second, rp.first, rp.second);
    return { o, distance(o, a) };
}

// 三角形内切圆， 需要三点不共线
circle inner (const point& a, const point& b, const point& c) {
    point ab = b - a;
    point ac = c - a;
    point ao = (ab / ab.length() + ac / ac.length()) / 2 + a;
    point ba = a - b;
    point bc = c - b;
    point bo = (ba / ba.length() + bc / bc.length()) / 2 + b;
    auto o = intersect(a, ao, b, bo);
    return { o, abs(distance(a, b, o)) };
}

// 求直线与圆的交点 保证有交点的情况下
pair<point, point> intersect(const point& lp, const point& rp, const circle& c) {
    point ft = foot(lp, rp, c.o);
    long double oft = distance(c.o, ft);
    long double k = sqrtl(c.r * c.r - oft * oft);
    point lr = (rp - lp) * k / distance(lp, rp);
    return { ft + lr, ft - lr };
}

// 求两圆的交点， 保证有交点
pair<point, point> intersect(const circle& lc, const circle& rc) {
    long double d = distance(lc.o, rc.o);
    long double k = ((lc.r * lc.r - rc.r * rc.r) / d + d) / 2;
    long double o = acos(k / lc.r);
    point lr = rc.o - lc.o;
    point lu = rotate(lr, o);
    lu = lu / lu.length() * lc.r;
    point ld = rotate(lr, -o);
    ld = ld / ld.length() * lc.r;
    return { lc.o + lu, lc.o + ld };
}

Convex-hull

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
vector<point> Andrew(vector<point> vp){
    sort(vp.begin(), vp.end(), [](const point& lp, const point& rp) -> bool {// X 第一关键字 Y 第二关键字
        if(lp.x == rp.x){
            return lp.y < rp.y;
        }
        return lp.x < rp.x;
    });
    int n = vp.size();
    vector<point> stk;
    for(int i = 0;i < n;i++){
        while(stk.size() > 1 && cross(stk.back() - stk[stk.size() - 2], vp[i] - stk.back()) <= 0){
            stk.pop_back();
        }
        stk.push_back(vp[i]);
    }
    int k = stk.size();
    for(int i = n - 2;i >= 0;i--){
        while(stk.size() > k && cross(stk.back() - stk[stk.size() - 2], vp[i] - stk.back()) <= 0){
            stk.pop_back();
        }
        stk.push_back(vp[i]);
    }
    stk.pop_back();
    return stk;
}

Nearest-points

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
//平面最近点对
long double nearest_points(vector<point> vp){
    sort(vp.begin(), vp.end(), [](const point& lp, const point& rp) -> bool {// X 第一关键字 Y 第二关键字
        if(lp.x == rp.x){
            return lp.y < rp.y;
        }
        return lp.x < rp.x;
    });

    const long double inf = 1e20;//最大值
    function<long double(int, int)> get = [&](int l, int r) -> long double {
        if(l == r){
            return inf;
        }

        if(l + 1 == r){
            return distance(vp[l], vp[r]);
        }

        int mid = (l + r) >> 1;
        long double ans = min(get(l, mid), get(mid + 1, r));//merge
        //合并
        vector<point> tmp;
        for(int i = l;i <= r;i++){
            if(fabsl(vp[i].x - vp[mid].x) < ans){
                tmp.push_back(vp[i]);
            }
        }
        sort(tmp.begin(), tmp.end(), [](const point& lp, const point& rp) -> bool {// Y 第一关键字 X 第二关键字
            if(lp.y == rp.y){
                return lp.x < rp.x;
            }
            return lp.y < rp.y;
        });

        for(int i = 0;i < tmp.size();i++){
            for(int j = i + 1;j < tmp.size() && tmp[j].y - tmp[i].y < ans;j++){
                ans = min(ans, distance(tmp[i], tmp[j]));
            }
        }

        return ans;
    };

    return get(0, vp.size() - 1);
}

Half plane

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
struct line {
    point lp;
    point rp;
    line(point _lp, point _rp){
        lp = _lp;
        rp = _rp;
    }
};

bool is_right(line a, line b, line c){//判断交点在直线右侧
    point p = intersect(b.lp, b.rp, c.lp, c.rp);
    return cross(a.rp - a.lp, p - a.lp) < 0;
}

long double half_plane(vector<line> ve){
    sort(ve.begin(), ve.end(), [](const line& le, const line& re) -> bool {//极角排序 + 左侧排序
        long double le_angle = polar_angle(le.rp - le.lp);
        long double re_angle = polar_angle(re.rp - re.lp);
        if(fabsl(le_angle - re_angle) < eps){
            return cross(le.rp - le.lp, re.rp - le.lp) < 0;// 注意是 re.rp - le.lp
        }
        return le_angle < re_angle;
    });

    deque<line> q;
    int n = ve.size();
    q.push_back(ve.front());
    for(int i = 1;i < n;i++){
        if(polar_angle(ve[i].rp - ve[i].lp) - polar_angle(ve[i - 1].rp - ve[i - 1].lp) < eps){
            continue;
        }

        while(q.size() > 1 && is_right(ve[i], q.back(), q[q.size() - 2])){
            q.pop_back();
        }

        while(q.size() > 1 && is_right(ve[i], q.front(), q[1])){
            q.pop_front();
        }
        q.push_back(ve[i]);
    }
    
    while(q.size() > 1 && is_right(q.front(), q.back(), q[q.size() - 2])){
        q.pop_back();
    }
    q.push_back(q.front());

    vector<point> tmp;
    for(int i = 0;i < q.size() - 1;i++){
        tmp.push_back(intersect(q[i].lp, q[i].rp, q[i + 1].lp, q[i + 1].rp));
    }

    long double ans = 0;
    for(int i = 1;i < tmp.size() - 1;i++){
        ans += cross(tmp[i] - tmp.front(), tmp[i + 1] - tmp.front());
    }

    return ans / 2.0;
}

Random-incremental

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
circle cover(const point& a, const point& b){
    return { (a + b) / 2, distance(a, b) / 2 };
}

//最小圆覆盖
circle increment(vector<point> vp){
    random_shuffle(vp.begin(), vp.end());//随机化
    int n = vp.size();
    circle ans = {vp.front(), 0};
    for(int i = 1;i < n;i++){
        if(ans.r < distance(ans.o, vp[i])){
            ans = {vp[i], 0};
            for(int j = 0;j < i;j++){
                if(ans.r < distance(ans.o, vp[j])){
                    ans = cover(vp[i], vp[j]);
                    for(int k = 0;k < j;k++){
                        if(ans.r < distance(ans.o, vp[k])){
                            ans = cover(vp[i], vp[j], vp[k]);
                        }
                    }
                }
            }
        }
    }
    return ans;
}

凸包最远点对

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
vector<point> Andrew(vector<point> vp){
    sort(vp.begin(), vp.end());
    int n = vp.size();
    vector<point> stk;
    for(int i = 0;i < n;i++){
        while(stk.size() > 1 && cross(stk.back() - stk[stk.size() - 2], vp[i] - stk.back()) <= 0){
            stk.pop_back();
        }
        stk.push_back(vp[i]);
    }
    int k = stk.size();
    for(int i = n - 2;i >= 0;i--){
        while(stk.size() > k && cross(stk.back() - stk[stk.size() - 2], vp[i] - stk.back()) <= 0){
            stk.pop_back();
        }
        stk.push_back(vp[i]);
    }
    stk.pop_back();
    return stk;
}

long long n;
cin >> n;
vector<point> vp(n);
for(int i = 0;i < n;i++){
    long long x, y;
    cin >> x >> y;
    vp[i] = { x, y };
}
auto convex = Andrew(vp);
int m = convex.size();
long double d = 0;
for(int i = 0, j = 1;i < m;i++){
    while(cross(convex[(i + 1) % m] - convex[i], convex[j] - convex[i]) < cross(convex[(i + 1) % m] - convex[i], convex[(j + 1) % m] - convex[i])){
        j = (j + 1) % m;
    }
    d = max(d, max(distance(convex[i], convex[j]), distance(convex[(i + 1) % m], convex[j])));
}