杭电多校 Asteroid In Love

发表于2020-08-14更新于2023-09-15字数统计1.5k阅读时长16分

Asteroid in Love

Description

给定平面 nn 个点，每个点可能是 0, 1, 2 三中类型中的一个。选出三个类型不同的点，使得三点形成的三角形面积最大。输出最大面积。

Solution

考虑已选了 2 个不同的点，则要使构成的三角形面积最大，第三个点一定在对应类型的凸包上，故先求出三类凸包。
对于同一直线，与第三点形成的三角形面积(叉积求面积，有正有负)在凸包上下凸壳分别具有单峰性，故可通过三分法求解。
三分法求解：下凸壳起点、终点，上凸壳起点、终点可以求出，设分别为 [1,up][1, up], [up,top][up, top]，那么只需要对这两个区间三分求极值(极大值、极小值)即可。

三分
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
inline LL trisection(const Vec2& a, const Vec2& b, int x, LL res = 0) { // x是点的类型
    LL l = 1, r = up[x]; //三分法 up是下凸壳终点，或上凸壳起点
    while (r - l >= 3) { //单峰
        LL lmid = (l + l + r) / 3;
        LL rmid = (l + r + r) / 3;
        LL ls = (cov[x][lmid] - a) * (cov[x][lmid] - b);
        LL rs = (cov[x][rmid] - a) * (cov[x][rmid] - b);
        if (ls > rs) r = rmid;
        else l = lmid;
    }
    for (int i = l; i <= r; i++) res = max(res, abs((cov[x][i] - a) * (cov[x][i] - b)));

    l = 1, r = up[x];
    while (r - l >= 3) { //单谷
        LL lmid = (l + l + r) / 3;
        LL rmid = (l + r + r) / 3;
        LL ls = (cov[x][lmid] - a) * (cov[x][lmid] - b);
        LL rs = (cov[x][rmid] - a) * (cov[x][rmid] - b);
        if (ls < rs) r = rmid;
        else l = lmid;
    }
    for (int i = l; i <= r; i++) res = max(res, abs((cov[x][i] - a) * (cov[x][i] - b)));

    l = up[x], r = top[x];
    while (r - l >= 3) { //单峰
        LL lmid = (l + l + r) / 3;
        LL rmid = (l + r + r) / 3;
        LL ls = (cov[x][lmid] - a) * (cov[x][lmid] - b);
        LL rs = (cov[x][rmid] - a) * (cov[x][rmid] - b);
        if (ls > rs) r = rmid;
        else l = lmid;
    }
    for (int i = l; i <= r; i++) res = max(res, abs((cov[x][i] - a) * (cov[x][i] - b)));

    l = up[x], r = top[x];
    while (r - l >= 3) { //单谷
        LL lmid = (l + l + r) / 3;
        LL rmid = (l + r + r) / 3;
        LL ls = (cov[x][lmid] - a) * (cov[x][lmid] - b);
        LL rs = (cov[x][rmid] - a) * (cov[x][rmid] - b);
        if (ls < rs) r = rmid;
        else l = lmid;
    }
    for (int i = l; i <= r; i++) res = max(res, abs((cov[x][i] - a) * (cov[x][i] - b)));
    return res;
}

注意：最后若用浮点数输出面积要用long double。

Code

Asteriod in Love
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
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
#include <bits/stdc++.h>

using namespace std;
using LL = long long;

constexpr LL MAXN = 3e3 + 3;

LL tc, n, top[3], up[3], cnt[3], ans;

struct Vec2 {
    Vec2() = default;
    Vec2(LL _x, LL _y) : x(_x), y(_y) {}

    friend inline Vec2 intersect(const Vec2&, const Vec2&, const Vec2&, const Vec2&);

    friend inline bool operator<(const Vec2& a, const Vec2& b) {
        return a.x == b.x ? a.y < b.y : a.x < b.x;
    }

    friend inline Vec2 operator-(const Vec2& a, const Vec2& b) {
        return Vec2(a.x - b.x, a.y - b.y);
    }

    friend inline Vec2 operator+(const Vec2& a, const Vec2& b) {
        return Vec2(a.x + b.x, a.y + b.y);
    }
    /*@return cross product of two Vec2*/
    friend inline LL operator*(const Vec2& a, const Vec2& b) {
        return a.x * b.y - a.y * b.x;  //×
    }
    /*@return 向量与数乘后的向量*/
    friend inline Vec2 operator*(const Vec2& a, LL num) {
        return Vec2(a.x * num, a.y * num);
    }
    /*@param a 2D vector @return norm of the vector*/
    friend inline LL norm(const Vec2& a) {
        return sqrt(a.x * a.x + a.y * a.y);
    }
    /*@param a 2D vector @return square norm of the vector*/
    friend inline LL normSquare(const Vec2& a) {
        return a.x * a.x + a.y * a.y;
    }

    LL x = 0, y = 0;
} vec[3][MAXN], cov[3][MAXN]/*三类凸包*/;

inline void convex(int x) { //x表示类型
    top[x] = up[x] = 0;
    sort(vec[x] + 1, vec[x] + cnt[x] + 1);
    LL& tp = top[x], &tmp = up[x];
    for (int i = 1; i <= cnt[x]; i++) {  //下凸壳
        while (tp > 1 && (cov[x][tp] - cov[x][tp - 1]) * (vec[x][i] - cov[x][tp]) <= 0)
            cov[x][tp--] = Vec2(0, 0);
        cov[x][++tp] = vec[x][i];
    }
    tmp = tp; //上凸壳起点
    for (int i = cnt[x] - 1; i > 0; i--) {  //上凸壳
        while (tp > tmp && (cov[x][tp] - cov[x][tp - 1]) * (vec[x][i] - cov[x][tp]) <= 0)
            cov[x][tp--] = Vec2(0, 0);
        cov[x][++tp] = vec[x][i];
    }
}

inline LL trisection(const Vec2& a, const Vec2& b, int x, LL res = 0) {
    LL l = 1, r = up[x]; //三分法
    while (r - l >= 3) { //单峰
        LL lmid = (l + l + r) / 3;
        LL rmid = (l + r + r) / 3;
        LL ls = (cov[x][lmid] - a) * (cov[x][lmid] - b);
        LL rs = (cov[x][rmid] - a) * (cov[x][rmid] - b);
        if (ls > rs) r = rmid;
        else l = lmid;
    }
    for (int i = l; i <= r; i++) res = max(res, abs((cov[x][i] - a) * (cov[x][i] - b)));

    l = 1, r = up[x];
    while (r - l >= 3) { //单谷
        LL lmid = (l + l + r) / 3;
        LL rmid = (l + r + r) / 3;
        LL ls = (cov[x][lmid] - a) * (cov[x][lmid] - b);
        LL rs = (cov[x][rmid] - a) * (cov[x][rmid] - b);
        if (ls < rs) r = rmid;
        else l = lmid;
    }
    for (int i = l; i <= r; i++) res = max(res, abs((cov[x][i] - a) * (cov[x][i] - b)));

    l = up[x], r = top[x];
    while (r - l >= 3) { //单峰
        LL lmid = (l + l + r) / 3;
        LL rmid = (l + r + r) / 3;
        LL ls = (cov[x][lmid] - a) * (cov[x][lmid] - b);
        LL rs = (cov[x][rmid] - a) * (cov[x][rmid] - b);
        if (ls > rs) r = rmid;
        else l = lmid;
    }
    for (int i = l; i <= r; i++) res = max(res, abs((cov[x][i] - a) * (cov[x][i] - b)));

    l = up[x], r = top[x];
    while (r - l >= 3) { //单谷
        LL lmid = (l + l + r) / 3;
        LL rmid = (l + r + r) / 3;
        LL ls = (cov[x][lmid] - a) * (cov[x][lmid] - b);
        LL rs = (cov[x][rmid] - a) * (cov[x][rmid] - b);
        if (ls < rs) r = rmid;
        else l = lmid;
    }
    for (int i = l; i <= r; i++) res = max(res, abs((cov[x][i] - a) * (cov[x][i] - b)));
    return res;
}

int main () {
    std::ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
    cout << setprecision(1) << fixed;
    cin >> tc;
    while (tc--) {
        cin >> n;
        ans = 0;
        memset(cnt, 0, sizeof(cnt));
        for (LL i = 1, x, y, type; i <= n; i++) {
            cin >> x >> y >> type;
            vec[type][++cnt[type]] = Vec2(x, y);
        }
        for (int type = 0; type < 3; type++) convex(type);
        for (int x = 0; x < 1; x++) //枚举星星类型
            for (int y = x + 1; y <= 2; y++)
                 for (int i = 1; i <= cnt[x]; i++)
                    for (int j = 1; j <= cnt[y]; j++)
                        ans = max(ans, trisection(vec[x][i], vec[y][j], 3 - x - y));
        long double res = ans; //注意精度
        cout << res / 2 << endl;
    }
    return 0;
}