QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#723641#9520. Concave Hullnan01WA 0ms3596kbC++2314.2kb2024-11-07 23:24:562024-11-07 23:24:56

Judging History

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

  • [2024-11-07 23:24:56]
  • 评测
  • 测评结果:WA
  • 用时:0ms
  • 内存:3596kb
  • [2024-11-07 23:24:56]
  • 提交

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;
    auto nxt = [&](int x)
    {
        return x % n + 1;
    };
    auto ret = area(h);
    ll mn = 2e18;
    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]));
    }
    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: 3552kb

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: -100
Wrong Answer
time: 0ms
memory: 3596kb

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:

2177206532877818119
1819399810238262553
1640902146749820538
1839362690072222871
2109987278957150842
894016174881844630
2270953324062222806
1994620728228843093
1714016191330242213
1167480950136890085

result:

wrong answer 1st lines differ - expected: '2178418010787347715', found: '2177206532877818119'