[旋转卡壳] HDU-6830 Asteroid in Love

During the summer vacation, the geoscience community launched a constellation observation activity.

On a clear night, Mira and Ao set up their telescopes. Through the telescopes, they observed $n$ stars. These n stars could be regarded as points on a two-dimensional plane, with coordinates $(x_i,y_i)$ .

It was boring to observe the stars alone, so they classified these stars into three categories according to their spectrum: R-type stars, G-type stars, and B-type stars.

Now, Mira wants to form a constellation named after Ao, for Ao to make up for the regret that there is no star named after Ao. This constellation should be small and beautiful. She wants the number of stars to be the least in this constellation. Besides, she wants the constellation contains all types of stars. It is easy to know that this constellation has only three stars, and the types of these three stars are R type, G type, and B type.

She also wants the area of the convex polygon enclosed by the stars of this constellation is the largest, that is, the area of the triangle formed by these three stars is the largest. If the triangle is trivial (that is, the three points that make up the triangle are on the same straight line), the area of the triangle is considered to be $0$ .

Please tell Mira the largest area of Constellation Ao.

Input

The first line contains an integer $T$ , indicating the number of testcase.

For each testcase, the first line contains a positive integer $n$ , indicating the number of stars observed.

From line $2$ to line $n+1$ , each line contains three integers $x,y,c$ . Line i describes the information of the stars $i−1$ , where x,y are the horizontal and vertical coordinates of the star's position, that is, the coordinates of the star are $(x,y)$ ; $c$ is for the description of stellar types, $0$ indicates that the stars are B-type stars, $1$ indicates R-type stars, and $2$ indicates G-type stars.

$T≤10,3≤n≤3×10^3,|x|,|y|≤10^9,0≤c≤2$

It is guaranteed that there exists a Constellation Ao, and any two stars will not be in the same position.

Output

For each testcase, output one real number per line indicates the maximum area. The answer should be rounded to one decimal place.

Sample Input

Sample Output

29.0
28.0

思路

题目就是给出 $3$ 个点集，现在要分别从这三个点集中选出一个点组成一个三角形，问三角形最大面积是多少。
最坏情况下每个点集只有 $1000$ 个点，所以考虑暴力枚举两个点，然后通过一些手段去寻找第三个点。
可以考虑枚举前两个点形成的一条直线，可以发现对于这两个点，如果想要形成的三角形面积最大，第三个点只可能是被直线切开的两个半平面中距离直线最远的点。那么先只考虑直线左侧的点，可以将直线极角排序，像旋转卡壳那样进行旋转，同时维护距离最远的点进行答案的更新即可。

代码

#include <bits/stdc++.h>
using namespace std;
void IO()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
}
typedef double db;
const db eps = 1e-9;
const db pi = acos(-1.0);
int sign(db k)
{
    if (k > eps)
        return 1;
    else if (k < -eps)
        return -1;
    return 0;
}
int cmp(db k1, db k2) { return sign(k1 - k2); }
int inmid(db k1, db k2, db k3) { return sign(k1 - k3) * sign(k2 - k3) <= 0; } // k3 在 [k1,k2] 内
struct point
{
    db x, y;
    point operator+(const point &k1) const { return (point){k1.x + x, k1.y + y}; }
    point operator-(const point &k1) const { return (point){x - k1.x, y - k1.y}; }
    point operator*(db k1) const { return (point){x * k1, y * k1}; }
    point operator/(db k1) const { return (point){x / k1, y / k1}; }
    point operator-() const { return (point){-x, -y}; }
    int operator==(const point &k1) const { return cmp(x, k1.x) == 0 && cmp(y, k1.y) == 0; }
    // 逆时针旋转
    point turn(db k1) { return (point){x * cos(k1) - y * sin(k1), x * sin(k1) + y * cos(k1)}; }
    point turn90() { return (point){-y, x}; }
    point turn270() { return (point){y, -x}; }
    bool operator<(const point k1) const
    {
        int a = cmp(x, k1.x);
        if (a == -1)
            return 1;
        else if (a == 1)
            return 0;
        else
            return cmp(y, k1.y) == -1;
    }
    db abs() { return sqrt(x * x + y * y); }
    db abs2() { return x * x + y * y; }
    db dis(point k1) { return ((*this) - k1).abs(); }
    point unit()
    {
        db w = abs();
        return (point){x / w, y / w};
    }
    friend istream &operator>>(istream &is, point &k)
    {
        is >> k.x >> k.y;
        return is;
    }
    friend ostream &operator<<(ostream &os, const point &k)
    {
        os << fixed << setprecision(2) << "(" << k.x << "," << k.y << ")\n";
        return os;
    }
    db getw() { return atan2(y, x); }
    point getdel()
    {
        if (sign(x) == -1 || (sign(x) == 0 && sign(y) == -1))
            return (*this) * (-1);
        else
            return (*this);
    }
    int getP() const { return sign(y) == 1 || (sign(y) == 0 && sign(x) == -1); }
};
int inmid(point k1, point k2, point k3) { return inmid(k1.x, k2.x, k3.x) && inmid(k1.y, k2.y, k3.y); }
inline db cross(point k1, point k2) { return k1.x * k2.y - k1.y * k2.x; }
db dot(point k1, point k2) { return k1.x * k2.x + k1.y * k2.y; }
db rad(point k1, point k2) { return atan2(cross(k1, k2), dot(k1, k2)); }
// -pi -> pi
bool compareangle(const point &k1, const point &k2)
{
    return k1.getP() < k2.getP() || (k1.getP() == k2.getP() && sign(cross(k1, k2)) > 0);
}
point proj(point k1, point k2, point q)
{ // q 到直线 k1,k2 的投影
    point k = k2 - k1;
    return k1 + k * (dot(q - k1, k) / k.abs2());
}
point reflect(point k1, point k2, point q) { return proj(k1, k2, q) * 2 - q; }
int clockwise(point k1, point k2, point k3)
{ // k1 k2 k3 逆时针 1 顺时针 -1 否则 0
    return sign(cross(k2 - k1, k3 - k1));
}
int checkLL(point k1, point k2, point k3, point k4)
{ // 求直线 (L) 线段 (S)k1,k2 和 k3,k4 的交点
    return cmp(cross(k3 - k1, k4 - k1), cross(k3 - k2, k4 - k2)) != 0;
}
point getLL(point k1, point k2, point k3, point k4)
{
    db w1 = cross(k1 - k3, k4 - k3), w2 = cross(k4 - k3, k2 - k3);
    return (k1 * w2 + k2 * w1) / (w1 + w2);
}
int intersect(db l1, db r1, db l2, db r2)
{
    if (l1 > r1)
        swap(l1, r1);
    if (l2 > r2)
        swap(l2, r2);
    return cmp(r1, l2) != -1 && cmp(r2, l1) != -1;
}
int checkSS(point k1, point k2, point k3, point k4)
{
    return intersect(k1.x, k2.x, k3.x, k4.x) && intersect(k1.y, k2.y, k3.y, k4.y) &&
           sign(cross(k3 - k1, k4 - k1)) * sign(cross(k3 - k2, k4 - k2)) <= 0 &&
           sign(cross(k1 - k3, k2 - k3)) * sign(cross(k1 - k4, k2 - k4)) <= 0;
}
db disSP(point k1, point k2, point q)
{
    point k3 = proj(k1, k2, q);
    if (inmid(k1, k2, k3))
        return q.dis(k3);
    else
        return min(q.dis(k1), q.dis(k2));
}
db disSS(point k1, point k2, point k3, point k4)
{
    if (checkSS(k1, k2, k3, k4))
        return 0;
    else
        return min(min(disSP(k1, k2, k3), disSP(k1, k2, k4)), min(disSP(k3, k4, k1), disSP(k3, k4, k2)));
}
int onS(point k1, point k2, point q) //点q在点k1,k2之间
{
    return inmid(k1, k2, q) && sign(cross(k1 - q, k2 - k1)) == 0;
}
struct circle
{
    point o;
    db r;
    int inside(point k) { return cmp(r, o.dis(k)); }
};
struct line
{
    // p[0]->p[1]
    point p[2];
    line(point k1, point k2)
    {
        p[0] = k1;
        p[1] = k2;
    }
    point &operator[](int k) { return p[k]; }
    int include(point k) { return sign(cross(p[1] - p[0], k - p[0])) > 0; }
    point dir() { return p[1] - p[0]; }
    line push()
    { // 向外 ( 左手边 ) 平移 eps
        const db eps = 1e-6;
        point delta = (p[1] - p[0]).turn90().unit() * eps;
        return {p[0] - delta, p[1] - delta};
    }
};
point getLL(line k1, line k2) { return getLL(k1[0], k1[1], k2[0], k2[1]); }
int parallel(line k1, line k2) { return sign(cross(k1.dir(), k2.dir())) == 0; }
int sameDir(line k1, line k2) { return parallel(k1, k2) && sign(dot(k1.dir(), k2.dir())) == 1; }
int operator<(line k1, line k2)
{
    if (sameDir(k1, k2))
        return k2.include(k1[0]);
    return compareangle(k1.dir(), k2.dir());
}
vector<point> ConvexHull(vector<point> A, int flag = 1) //凸包
{                           // flag=0 不严格 flag=1 严格
    int n = A.size();
    vector<point> ans(n * 2);
    sort(A.begin(), A.end());
    int now = -1;
    for (int i = 0; i < A.size(); i++)
    {
        while (now > 0 && sign(cross(ans[now] - ans[now - 1], A[i] - ans[now - 1])) < flag)
            now--;
        ans[++now] = A[i];
    }
    int pre = now;
    for (int i = n - 2; i >= 0; i--)
    {
        while (now > pre && sign(cross(ans[now] - ans[now - 1], A[i] - ans[now - 1])) < flag)
            now--;
        ans[++now] = A[i];
    }
    ans.resize(now);
    return ans;
}

//-----------------------------
vector<vector<point>> vp(3);
vector<line> vl;
int n;

inline long double spcross(const point &k1, const point &k2)
{
    return (long double)k1.x * k2.y - (long double)k1.y * k2.x;
}

void solve()
{
    cin >> n;
    for (int i = 0; i < 3; i++)
        vp[i].clear();
    vl.clear();
    for (int i = 0, color; i < n; i++)
    {
        point tem;
        cin >> tem >> color;
        vp[color].push_back(tem);
    }
    sort(vp.begin(), vp.end(), [](const vector<point> &k1, const vector<point> &k2) {
        return k1.size() < k2.size();
    });

    if (vp[2].size() > 2)
        vp[2] = ConvexHull(vp[2]);

    for (int i = 0; i < vp[0].size(); i++)
        for (int j = 0; j < vp[1].size(); j++)
            vl.push_back({vp[0][i], vp[1][j]});
    sort(vl.begin(), vl.end());

    int i = 0, j = 0, sz = vp[2].size();
    db ansi = -1e21, ansj = 1e21;
    long double ans = -1;
    point p1 = vl[0][0], p2 = vl[0][1];
    for (int id = 0; id < vp[2].size(); id++)
    {
        db tem = (cross(p2 - p1, vp[2][id] - p1));
        if (cmp(tem, ansi) > 0)
        {
            ansi = tem;
            i = id;
        }
    }
    for (int id = 0; id < vp[2].size(); id++)
    {
        db tem = (cross(p2 - p1, vp[2][id] - p1));
        if (cmp(tem, ansj) < 0)
        {
            ansj = tem;
            j = id;
        }
    }
    for (auto &x : vl)
    {
        point p1 = x[0], p2 = x[1];

        while (cmp((cross(p2 - p1, vp[2][i] - p1)), cross(p2 - p1, (vp[2][(i + 1) % sz] - p1))) < 0)
            i = (i + 1) % sz;
        while (cmp((cross(p2 - p1, vp[2][j] - p1)), cross(p2 - p1, (vp[2][(j + 1) % sz] - p1))) > 0)
            j = (j + 1) % sz;
        ans = max({ans, fabs(spcross(p2 - p1, vp[2][i] - p1)), fabs(spcross(p2 - p1, vp[2][j] - p1))});
    }
    cout << fixed << setprecision(1) << ans / 2 << '\n';
}

int main()
{
    IO();
    int _;
    cin >> _;
    while (_--)
        solve();
}

吐槽

由于答案很大， $double$ 可能会爆精度，比赛的时候就因为这个 $wa$ 的。