QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#723668#9520. Concave Hullnan01RE 1ms3852kbC++2314.5kb2024-11-07 23:32:222024-11-07 23:32:24

Judging History

你现在查看的是最新测评结果

  • [2024-11-07 23:32:24]
  • 评测
  • 测评结果:RE
  • 用时:1ms
  • 内存:3852kb
  • [2024-11-07 23:32:22]
  • 提交

answer

#include <bits/stdc++.h>
#define rep(i, a, n) for (int i = a; i <= n; i++)
#define per(i, a, n) for (int i = n; i >= a; i--)
#define ll long long
#define pii pair<int, int>
#define inf 0x3f3f3f3f
#define fi first
#define pll pair<ll, ll>
#define se second
#define lll __int128
#define ld long double
#define all(a) a.begin() + 1, a.end()
#define iofast                   \
    ios::sync_with_stdio(false); \
    cin.tie(0), cout.tie(0)
#define lowbit(i) (i & (-i))
using namespace std;
const int maxn = 1e6 + 5, mod = 1000000007;
// 三角形重心是 (x1+ x2+x3)/3, (y1+y2 + y3)/3
// if 外心= (0,0)
// -> 垂心=(x1+x2+x3, y1+y2+y3) (欧拉线:重心,外心,垂心共线,2*dis(外心,重心)=dis(重心,垂心)
// 内心=角平分线交点,角平分线与外接圆的三个交点组成的三角形的垂心等于原三角形的内心
const double eps = 1e-10;
int sgn(double a)
{
    if (fabs(a) < eps)
        return 0;
    if (a < 0)
        return -1;
    return 1;
}
template <class T>
class point
{
public:
    T x, y;
    point(T a, T b) : x(a), y(b) {}
    point() {};
    point operator+(point a) { return point(x + a.x, y + a.y); }
    point operator-(point a) { return point(x - a.x, y - a.y); }
    point operator*(double a) { return point(x * a, y * a); }
    point operator/(double a) { return point(x / a, y / a); }
    T operator*(point a) { return x * a.x + y * a.y; }
    T operator%(point a) { return x * a.y - y * a.x; }
    bool operator==(point a) { return x == a.x && y == a.y; }
    friend istream &operator>>(istream &is, point<T> &x)
    {
        is >> x.x >> x.y;
        return is;
    }
    friend ostream &operator<<(ostream &os, const point<T> &x) { return os << x.x << " " << x.y; }
};
template <class T>
struct circle
{
    point<T> o;
    T r;
};
template <class T>
class line
{
public:
    point<T> s, t;
};
template <typename T>
T mul(point<T> a, point<T> b, point<T> c) // c和ab叉乘 当ca逆时针转小于180度遇到cb时为正
{
    return (c - a) % (c - b);
}
template <typename T>
T dot(point<T> a, point<T> b, point<T> c) // ab和ac点乘
{
    return (a - b) * (a - c);
}
template <typename T>
point<T> interpoint(point<T> s1, point<T> t1, point<T> s2, point<T> t2) // 向量交点
{
    auto t = fabs(((t2 - s2) % (s2 - s1)) / ((t2 - s2) % (t1 - s1)));
    return s1 + (t1 - s1) * fabs(((t2 - s2) % (s2 - s1)) / ((t2 - s2) % (t1 - s1)));
}
template <typename T>
point<T> cross(point<T> a, point<T> b, point<T> c, point<T> d) // 直线交点
{
    auto v = c - d;
    ld sa = v % (a - d), sb = (b - d) % v;
    ld rate = sa / (sa + sb);
    return (b - a) * rate + a;
}
template <typename T>
inline bool parallel(point<T> s1, point<T> t1, point<T> s2, point<T> t2) // 判断平行 最好用整数point,别用double
{
    return ((t1 - s1) % (t2 - s2)) == 0;
}
template <typename T>
inline bool isinseg(point<T> s, point<T> t, point<T> mid) // 判断mid是否在st线段内,double改成eps
{
    return dot(mid, s, t) <= 0;
}
template <typename T>
double dis(point<T> a, point<T> b) // ab距离
{
    return sqrt((a - b) * (a - b));
}
template <typename T>
T distoline(point<T> a, point<T> b, point<T> c) // c到ab直线距离
{
    auto u = a - b, v = a - c;
    return fabs(u % v / dis(a, b));
}
template <typename T>
T distoseg(point<T> a, point<T> b, point<T> c) // c到ab线段距离
{
    auto u = b - a, v = c - a, w = c - b;
    if (a == b)
        return dis(c, b);
    if (u * v < 0)
        return dis(c, a);
    if (u * w > 0)
        return dis(b, c);
    return distoline(a, b, c);
}
template <typename T>
T sqadis(point<T> a, point<T> b) // ab平方距离
{
    return (a - b) * (a - b);
}
template <typename T>
bool cmp(point<T> a, point<T> b) // x第一关键字,y第二关键字
{
    return a.x == b.x ? a.y < b.y : a.x < b.x;
}
template <typename T>
point<T> rot(point<T> a) // 逆时针旋转90
{
    return point{-a.y, a.x};
}
template <typename T>
point<T> rotate(point<T> a, double angle) // 顺时针旋转angle度
{
    return point{a.x * cos(angle) + a.y * sin(angle), -a.x * sin(angle) + a.y * cos(angle)};
}
template <typename T>
double angle(point<T> a, point<T> b, point<T> c) // 返回b-a和c-a的tan值 垂直则返回-1;
{
    auto v1 = b - a;
    auto v2 = c - a;
    if (v1 * v2 == 0)
        return -1;
    return double(v1 % v2) / (v1 * v2);
}
template <typename T>
point<T> excir(point<T> a, point<T> b, point<T> c) // 求外接圆圆心
{
    auto d1 = (a + b) * 0.5, d2 = d1 + rot(a - b);
    auto d3 = (c + b) * 0.5, d4 = d3 + rot(c - b);
    return cross(d1, d2, d3, d4);
}
template <typename T>
bool check(circle<T> a, point<T> b) // 判断点是否在圆外
{
    if (dis(a.o, b) - a.r > eps)
        return false;
    else
        return 1;
}
template <typename T>
circle<T> smallestcircle(vector<point<T>> a) // 最小覆盖圆
{
    int n = a.size() - 1;
    random_shuffle(a.begin() + 1, a.begin() + n + 1);
    circle<T> c{a[1], 0};
    rep(i, 2, n)
    {
        if (!check(c, a[i]))
        {
            c = circle<T>{a[i], 0};
            rep(j, 1, i - 1)
            {
                if (!check(c, a[j]))
                {
                    c = circle<T>{(a[i] + a[j]) * 0.5, dis(a[i], a[j]) / 2.0};
                    rep(k, 1, j - 1)
                    {
                        if (!check(c, a[k]))
                        {
                            point<double> o = excir(a[i], a[j], a[k]);
                            c = circle<T>{o, dis(o, a[i])};
                        }
                    }
                }
            }
        }
    }
    return c;
}
template <typename T>
bool isinter(point<T> a, point<T> b, point<T> c, point<T> d) // 两线段是否相交
{
    double c1 = (c - a) % (b - a), c2 = (d - a) % (b - a);
    double c3 = (b - d) % (c - d), c4 = (a - d) % (c - d);
    return sgn(c1) * sgn(c2) < 0 && sgn(c3) * sgn(c4) < 0;
}
template <typename T>
vector<point<T>> graham(vector<point<T>> p, bool flag = 1) // 求凸包  1-index
{
    sort(all(p), cmp<T>);
    int n = p.size() - 1;
    vector<point<T>> h(n + 2);
    h[1] = p[1];
    int m = 1;
    rep(i, 2, n)
    {
        while (m > 1 && mul(h[m - 1], h[m], p[i]) <= 0)
            m--;
        h[++m] = p[i];
    }
    int k = m;
    for (int i = n - 1; i >= 1; i--)
    {
        while (m > k && mul(h[m - 1], h[m], p[i]) <= 0)
            m--;
        h[++m] = p[i];
    }
    h.resize(m + flag); // flag=1 不删除最后一个点 反之删除  最后一个点也是第一个点
    return h;
}
template <typename T>
bool ispointinhull(vector<point<T>> p, point<T> a) // log判断点是否再凸包内
{
    int n = p.size() - 1;
    int l = 0, r = n;
    while (l < r - 1)
    {
        int mid = l + r >> 1;
        T x = mul(p[mid], a, p[0]);
        T y = mul(p[mid + 1], a, p[0]);
        if (sgn(x) >= 0 && sgn(y) <= 0)
        {
            if (sgn(mul(p[mid + 1], a, p[mid])) >= 0)
            {
                return 1;
            }
            return 0;
        }
        else if (sgn(y) > 0)
            l = mid;
        else
            r = mid;
    }
    return 0;
}
template <typename T>
double zuijindiandui(vector<point<T>> a) // 最近公共点对
{
    sort(all(a), cmp<T>);
    double mn = 2e18;
    int n = a.size() - 1;
    auto cal = [&](auto self, int l, int r) -> void
    {
        if (l == r)
            return;
        int m = l + r >> 1;
        self(self, l, m);
        self(self, m + 1, r);
        double mid = (a[m].x + a[m + 1].x) / 2;
        int L = m;
        while (L >= l && a[L].x >= mid - mn)
        {
            L--;
        }
        L++;
        int R = m + 1;
        while (R <= r && a[R].x <= mid + mn)
            R++;
        R--;
        rep(i, L, m)
        {
            rep(j, m + 1, R)
            {
                mn = min(mn, dis(a[i], a[j]));
            }
        }
    };
    cal(cal, 1, n);
    return mn;
}
template <typename T>
T xzkk(vector<point<T>> a) // 旋转卡壳
{
    a = graham(a, 0); // 要删掉最后一个点!
    T mx = 0;
    int j = 3;
    int n = a.size() - 1;
    if (n == 2) // 如果是直线
    {
        return dis(a[1], a[2]);
    }
    a.push_back(a[1]);
    rep(i, 1, n)
    {
        mx = max(mx, dis(a[i], a[i + 1]));
        while (llabs(mul(a[i], a[i + 1], a[j])) <= llabs(mul(a[i], a[i + 1], a[j + 1])))
            j = (j % n) + 1;
        mx = max(mx, max(dis(a[i], a[j]), dis(a[i + 1], a[j])));
    }

    return mx;
}
template <typename T>
double angle(line<T> a) // 直线的极角
{
    return atan2(a.t.y - a.s.y, a.t.x - a.s.x);
}
template <typename T>
inline point<T> cross(line<T> a, line<T> b) // 两直线交点
{
    return cross(a.s, a.t, b.s, b.t);
}
template <typename T>
bool right(line<T> a, line<T> b, line<T> c) // bc交点时候在a右边
{
    auto d = cross(b, c);
    return mul(a.s, a.t, d) < 0; // 在线上不算
}
template <typename T>
bool left(line<T> a, line<T> b, line<T> c) // bc交点时候在a右边
{
    auto d = cross(b, c);
    return mul(a.s, a.t, d) >= 0; // 在线上算
}

template <typename T>
vector<point<T>> halfplane(vector<line<T>> a) // 半平面交
{
    sort(all(a), [&](auto a, auto b)
         { double x = angle(a), y = angle(b);
        return fabs(x-y) > eps ? x<y : mul(b.s, b.t, a.t) > 0; });
    deque<line<T>> q;
    q.push_back(a[1]);
    rep(i, 2, (int)a.size() - 1)
    {
        if (fabs(angle(a[i]) - angle(q.back()) < eps))
            continue;
        while (q.size() > 1)
        {
            auto t = q.back();
            q.pop_back();
            if (left(a[i], t, q.back()))
            {
                q.push_back(t);
                break;
            }
        }
        while (q.size() > 1)
        {
            auto t = q.front();
            q.pop_front();
            if (left(a[i], t, q.front()))
            {
                q.push_front(t);
                break;
            }
        }
        q.push_back(a[i]);
    }
    while (q.size() > 2)
    {
        auto t = q.back();
        q.pop_back();
        if (left(q.front(), t, q.back()))
        {
            q.push_back(t);
            break;
        }
    }
    int siz = q.size();
    q.push_back(q.front());
    vector<point<T>> ret(1); // 1-index
    rep(i, 1, siz)
    {
        auto t = q.front();
        q.pop_front();
        ret.push_back(cross(t, q.front()));
    }
    return ret;
}
template <typename T>
ll area(vector<point<T>> a) // 一个凸包求面积
{
    int siz = a.size() - 1;
    ll ret = 0;
    rep(i, 2, siz - 1)
    {
        ret += mul(a[1], a[i], a[i + 1]);
    }
    return ret;
}
template <typename T>
struct matrix
{
    point<T> a, b, c, d;
    T area;
    matrix(point<T> a, point<T> b, point<T> c, point<T> d, T area = 0) : a(a), b(b), c(c), d(d), area(area) {}
    matrix() : area(0) {}
};
template <typename T>
matrix<T> minmatcover(vector<point<T>> p) // p为1-index  最小矩形覆盖 (最小正方形覆盖三分)
{
    p = graham(p);
    int n = (int)p.size() - 2;
    p[0] = p[n];
    // j右边 k上边 h左边
    double ret = 2e18;
    array<int, 4> ansi;
    for (int i = 1, j = 1, k = 2, h = -1; i <= n; i++)
    {
        // cout << p[i].x << " " << p[i].y << endl;
        auto cur = p[i + 1] - p[i];
        while ((p[j + 1] - p[i]) * (cur)-eps > (p[j] - p[i]) * (cur))
        {
            j = (j % n) + 1;
        }
        while (mul(p[i + 1], p[k], p[i]) < mul(p[i + 1], p[k + 1], p[i]) - eps)
        {
            k = (k % n) + 1;
        }
        if (h == -1)
            h = k;
        while ((p[h + 1] - p[i]) * (cur) < (p[h] - p[i]) * (cur)-eps)
        {
            h = (h % n) + 1;
        }
        // cout << j << " " << k << " " << h << endl;
        double len = ((p[j] - p[i]) * (cur) - (p[h] - p[i]) * (cur)) / dis(p[i], p[i + 1]);
        double wid = distoline(p[i], p[i + 1], p[k]);
        // cout << len * wid << "\n";
        if (ret > len * wid)
        {
            ret = len * wid;
            ansi = array{i, j, k, h};
        }
    }
    matrix<T> res;
    {
        auto [i, j, k, h] = ansi;
        auto t = (p[i + 1] - p[i]) / dis(p[i + 1], p[i]);  // 矩形一条边的单位向量
        auto x = t * (t * (p[j] - p[i]));                  // 最右边的点的在该单位向量上的影射
        auto y = rot(t) * distoline(p[i], p[i + 1], p[k]); // 矩形的宽的向量
        auto z = t * (t * (p[h] - p[i]));                  // 最左边的点的在该单位向量上的影射

        res.a = (x + p[i]);
        res.b = (x + y + p[i]);
        res.c = (z + y + p[i]);
        res.d = (z + p[i]);
        res.area = ret;
    }
    return res; // 按照逆时针排序矩形四个点
}
void solve()
{
    int n;
    cin >> n;
    vector<point<ll>> a(n + 1);
    rep(i, 1, n)
    {
        cin >> a[i];
    }
    auto h = graham(a);
    vector<int> cnt(n + 1);
    sort(all(a), cmp<ll>);
    vector<point<ll>> b(1);
    int j = 1;
    for (int i = 1; i <= n; i++)
    {
        if (a[i] == h[j])
        {
            j++;
            continue;
        }
        cnt[i]++;
        // b.push_back(a[i]);
    }
    for (int i = n; i > 0; i--)
    {
        if (a[i] == h[j])
        {
            j++;
            continue;
        }
        cnt[i]++;
    }
    for (int i = 1; i <= n; i++)
    {
        if (cnt[i] == 2)
        {
            b.push_back(a[i]);
        }
    }
    if (b.size() == 1)
    {
        cout << -1 << endl;
        return;
    }
    auto h2 = graham(b, 0);
    j = 1;
    n = h.size() - 2;
    int m = h2.size() - 1;
    auto nxt = [&](int x)
    {
        return x % n + 1;
    };
    auto ret = area(h);
    ll mn = 2e18;
    for (int i = 1; i <= n; i++)
    {
        while (mul(h[i], h[nxt(i)], h2[j]) >= mul(h[i], h[nxt(i)], h2[j % m + 1]))
        {
            j = j % m + 1;
        }
        mn = min(mn, mul(h[i], h[nxt(i)], h2[j]));
    }
    // for (int i = 1; i < h2.size(); i++)
    // {
    //     while (mul(h[j], h[nxt(j)], h2[i]) >= mul(h[nxt(j)], h[nxt(nxt(j))], h2[i]))
    //     {
    //         j = nxt(j);
    //     }
    //     mn = min(mn, mul(h[j], h[nxt(j)], h2[i]));
    // }
    assert(mn >= 0);
    cout << ret - mn << endl;
}
int main()
{
    iofast;
    int t = 1;
    cin >> t;
    while (t--)
        solve();
    // cout << endl;
    //  system("pause");
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 0ms
memory: 3620kb

input:

2
6
-2 0
1 -2
5 2
0 4
1 2
3 1
4
0 0
1 0
0 1
1 1

output:

40
-1

result:

ok 2 lines

Test #2:

score: 0
Accepted
time: 1ms
memory: 3852kb

input:

10
243
-494423502 -591557038
-493438474 -648991734
-493289308 -656152126
-491185085 -661710614
-489063449 -666925265
-464265894 -709944049
-447472922 -737242534
-415977509 -773788538
-394263365 -797285016
-382728841 -807396819
-373481975 -814685302
-368242265 -818267002
-344482838 -833805545
-279398...

output:

2178418010787347715
1826413114144932145
1651687576234220014
1883871859778998985
2119126281997959892
894016174881844630
2271191316922158910
1998643358049669416
1740474221286618711
1168195646932543192

result:

ok 10 lines

Test #3:

score: -100
Runtime Error

input:

1000
125
64661186 -13143076
302828013 -185438065
-418713797 -191594241
430218126 -397441626
354327250 -836704374
149668812 -598584998
311305970 66790541
199720625 -592356787
468137 -584752683
258775829 96211747
-358669612 -134890109
-129221188 -998432368
-277309896 -140056561
356901185 420557649
-51...

output:

1986320445246155278
1900093336073022078
1612088392301142476
2012259136539173407
1819942017252118749
1772230185841892196
1164835025329039520
1527446155241140517
1807368432185303666
1236918659444944569
1306839249967484778
1984123720246784099
1868728080720036006
667458140583450322
2127932992585026491

result: