QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#768289#9520. Concave HullDopplerXDWA 1ms3832kbC++2025.6kb2024-11-21 08:43:252024-11-21 08:43:26

Judging History

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

  • [2024-11-21 08:43:26]
  • 评测
  • 测评结果:WA
  • 用时:1ms
  • 内存:3832kb
  • [2024-11-21 08:43:25]
  • 提交

answer

#include <iostream>
#include <iomanip>
#include <algorithm>
#include <map>
#include <set>
#include <queue>
#include <string>
#include <cstring>
#include <cmath>
#include <list>
#include <stack>
#include <array>
#include <unordered_map>
#include <unordered_set>
#include <bitset>
#include <random>
#include <numeric>
#include <functional>
//#include <Windows.h>

using namespace std;

#define fa(i,op,n) for (int i = op; i <= n; i++)
#define fb(j,op,n) for (int j = op; j >= n; j--)
#define pb push_back
#define HashMap unordered_map
#define HashSet unordered_set
#define var auto
#define all(i) i.begin(), i.end()
#define all1(i) i.begin() + 1,i.end()
#define endl '\n'
#define px first
#define py second

using VI = vector<int>;
using VL = vector<long long>;
using ll = long long;
using ull = unsigned long long;
using db = double;
using pii = pair<int, int>;
using pll = pair<ll, ll>;

template<class T1, class T2>
ostream& operator<<(ostream& out, const pair<T1, T2>& p) {
    out << '(' << p.first << ", " << p.second << ')';
    return out;
}

template<typename T>
ostream& operator<<(ostream& out, const vector<T>& ve) {
    for (T i : ve)
        out << i << ' ';
    return out;
}

template<class T1, class T2>
ostream& operator<<(ostream& out, const map<T1, T2>& mp) {
    for (auto i : mp)
        out << i << '\n';
    return out;
}

template<typename ...T>
bool _debug(T... a) {
    ((cout << a << ' '), ...);
    cout << endl;
    return -1;
}

const int INF = 0x3f3f3f3f;
const ll LNF = 0x3f3f3f3f3f3f3f3f;
const int IINF = 0x7fffffff;
const int iinf = 0x80000000;
const ll LINF = 0x7FFFFFFFFFFFFFFF;
const ll linf = 0x8000000000000000;
int dx[8] = {1, -1, 0, 0, 1, -1, 1, -1};
int dy[8] = {0, 0, 1, -1, 1, -1, -1, 1};

//#include "Lynia.h"
namespace MyTools
{
    template <typename T>
    class Math;

    template <const int T>
    class ModInt;

    namespace Geo {
        template<typename T>
        class Point;

        template<typename T>
        class Line;

        template<typename T>
        class Polygon;

        template<typename T>
        class Circle;

        template<typename T>
        using Vector = Point<T>;

        template<typename T>
        using Segment = Line<T>;

        const double eps = 1e-8;
        const double PI = acos(-1.0);

        // 浮点数 x 的符号
        template<typename T>
        int sgn(T x) {
            if (fabs(x) < eps) return 0;
            return x > 0 ? 1 : -1;
        }

        // 比较两个浮点数
        template<typename T>
        int cmp(T x, T y) {
            if (fabs(x) < eps)return 0; // x == y,返回 0
            else return x < y ? -1 : 1; // x < y,返回 -1; x > y,返回 1
        }

        double radians(double degrees) {
            return degrees * PI / 180.0;
        }

        // 两点距离
        template<typename T>
        T dist(const Point<T>& A, const Point<T>& B) {
            return sqrt((A.x - B.x) * (A.x - B.x) + (A.y - B.y) * (A.y - B.y));
        }

        // 点积
        template<typename T>
        T dot(const Vector<T>& A, const Vector<T>& B) {
            // a · b = |a| |b| cos
            // 可用于判断两向量夹角
            return A.x * B.x + A.y * B.y;
        }

        // 叉积
        template<typename T>
        T cross(const Vector<T>& A, const Vector<T>& B) {
            // a · b = |a| |b| sin
            // 可以判断两向量的相对方向
            // 也能算两向量形成的平行四边形面积
            return A.x * B.y - A.y * B.x;
        }

        // 向量长度
        template<typename T>
        T len(const Vector<T>& A) {
            return sqrt(dot(A, A));
        }

        // 向量长度的平方
        template<typename T>
        T len2(const Vector<T>& A) {
            return dot(A, A);
        }

        // 两向量夹角
        template<typename T>
        double angle(const Vector<T>& A, const Vector<T>& B) {
            return acos(dot(A, B) / len(A) / len(B));
        }

        // 计算两向量构成的平行四边形有向面积
        // 三个点A、B、C,以A为公共点,得到2个向量B-A和C-A,它们构成的平行四边形
        template<typename T>
        T area_parallelogram(const Point<T>& A, const Point<T>& B, const Point<T>& C) {
            return -cross(B - A, C - A);
        }

        // 计算两向量构成的平行四边形有向面积
        // 两个有公共点的向量 A B 构成的平行四边形
        // A B 要按逆时针顺序
        template<typename T>
        T area_parallelogram(const Vector<T>& A, const Vector<T>& B) {
            return cross(A, B);
        }

        // 计算两向量构成的三角形有向面积
        // 三个点A、B、C,以A为公共点,得到2个向量B-A和C-A,它们构成的三角形
        template<typename T>
        T area_triangle(const Point<T>& A, const Point<T>& B, const Point<T>& C) {
            return -cross(B - A, C - A) / 2.0;
        }

        // 计算两向量构成的三角形有向面积
        // 两个有公共点的向量 A B 构成的三角形
        // A B 要按逆时针顺序
        template<typename T>
        T area_triangle(const Vector<T>& A, const Vector<T>& B) {
            return cross(A, B) / 2.0;
        }

        // 向量旋转	
        /*
            特殊情况是旋转90度:
            逆时针旋转90度:Rotate(A, pi/2),返回Vector(-A.y, A.x);
            顺时针旋转90度:Rotate(A, -pi/2),返回Vector(A.y, - A.x)。
        */
        template<typename T>
        Vector<T> rotate(const Vector<T>& A, double rad) {
            return Vector<T>(A.x * cos(rad) - A.y * sin(rad), A.x * sin(rad) + A.y * cos(rad));
        }

        // 有时需要求单位法向量,即逆时针转90度,然后取单位值。
        template<typename T>
        Vector<T> normal(const Vector<T>& A) {
            return Vector<T>(-A.y / len(A), A.x / len(A));
        }

        // 两个向量是否平行或重合
        template<typename T>
        bool parallel(const Vector<T>& A, const Vector<T>& B) {
            return sgn(cross(A, B)) == 0; // 返回true表示平行或重合
        }

        // 点和直线的位置关系
        template<typename T>
        int point_line_relation(const Point<T>& p, const Line<T>& v) {
            int c = sgn(cross(p - v.p1, v.p2 - v.p1));
            if (c < 0)return 1;              // 1 :p在v的左边
            if (c > 0)return 2;              // 2 :p在v的右边
            return 0;                        // 0 :p在v上
        }

        // 点和线段的位置关系
        template<typename T>
        bool point_segment_relation(const Point<T>& p, const Line<T>& v) {
            // 0 点不在线段v上
            // 1 点在线段v上

            // 前者为 True 说明 p 和 线段 v 的一个端点连边,和 v 本身的夹角为 0,即 p 在 直线 v 上
            // 后者为 True 说明 p 和两端点形成平角,也就是说 p 在两端点之间
            return sgn(cross(p - v.p1, v.p2 - v.p1)) == 0 && sgn(dot(p - v.p1, p - v.p2)) <= 0;
        }

        // 点到直线的距离
        template<typename T>
        double point_line_dis(const Point<T>& p, const Line<T>& v) {
            // 实际上是算了 p 和 v 的一个端点连边,然后和 v 形成的平行四边形的面积,除底得到
            return fabs(cross(p - v.p1, v.p2 - v.p1)) / dist(v.p1, v.p2);
        }

        // 点在直线上的投影
        template<typename T>
        Point<T> point_line_proj(const Point<T>& p, const Line<T>& v) {
            double k = dot(v.p2 - v.p1, p - v.p1) / len2(v.p2 - v.p1);
            return v.p1 + (v.p2 - v.p1) * k;
        }

        // 点关于直线的对称点
        template<typename T>
        Point<T> point_line_symmetry(const Point<T>& p, const Line<T>& v) {
            Point<T> q = point_line_proj(p, v);
            return Point<T>(2 * q.x - p.x, 2 * q.y - p.y);
        }

        // 点到线段的距离
        template<typename T>
        double point_segment_dis(const Point<T>& p, const Segment<T>& v) {
            // 先检查点 p 到线段 v 的投影是否在线段 v 上
            // 如果在,就直接返回点 p 到直线 v 距离
            // 如果不在,就返回线段 v 两端点里 p 

            // p 先和 v 的两端点比较,看看是否两向量夹角 > 90
            if (sgn(dot(p - v.p1, v.p2 - v.p1)) < 0 || sgn(dot(p - v.p2, v.p1 - v.p2)) < 0)
                return min(dist(p, v.p1), dist(p, v.p2)); // 点的投影不在线段上
            return point_line_dis(p, v);           // 点的投影在线段上
        }

        // 叉积判断两条向量的位置关系,AB * AC,两向量共点
        template<typename T>
        int vector_vector_relation(const Vector<T>& v1, const Vector<T>& v2) {
            int sign = sgn(cross(v1, v2));
            if (sign == 0)return 0; // 共线
            if (sign > 0)return 1;  // v2 在 v1 的逆时针方向 
            if (sign < 0)return 2;  // v2 在 v1 的顺时针方向 
        }

        // 叉积判断两条直线的位置关系
        template<typename T>
        int line_line_relation(const Line<T>& v1, const Line<T>& v2) {
            if (sgn(cross(v1.p2 - v1.p1, v2.p2 - v2.p1)) == 0) {
                if (point_line_relation(v1.p1, v2) == 0) return 1;  // 1: 重合
                else return 0;                                      // 0: 平行
            }
            return 2;                                               // 2: 相交
        }

        // 两向量夹角类型
        template<typename T>
        int vector_vector_angle_type(const Vector<T>& v1, const Vector<T>& v2) {
            // 0:夹角度为 0
            // 1:夹角为锐角
            // 2:夹角为钝角
            // 3:夹角为平角,即方向相反
            var _dot = dot(v1, v2);
            if (vector_vector_relation(v1, v2) == 0) { // 两向量共线
                if (sgn(_dot) > 0)return 0;
                else return 3;
            }
            else {
                if (sgn(_dot) > 0)return 1;
                else return 2;
            }
        }

        // 两条直线的交点
        template<typename T>
        Point<T> line_line_cross_point(const Point<T>& a, const Point<T>& b, const Point<T>& c, const Point<T>& d) {
            // Line1 : ab, Line2 : cd
            double s1 = cross(b - a, c - a);
            double s2 = cross(b - a, d - a);                    // 叉积有正负
            return Point<T>(c.x * s2 - d.x * s1, c.y * s2 - d.y * s1) / (s2 - s1);
        }

        // 两条直线的交点
        template<typename T>
        Point<T> line_line_cross_point(const Line<T>& x, const Line<T>& y) {
            // Line1 : ab, Line2 : cd
            var a = x.p1;
            var b = x.p2;
            var c = y.p1;
            var d = y.p2;
            double s1 = cross(b - a, c - a);
            double s2 = cross(b - a, d - a);                    // 叉积有正负
            return Point<T>(c.x * s2 - d.x * s1, c.y * s2 - d.y * s1) / (s2 - s1);
        }

        // 两个线段是否相交
        template<typename T>
        bool segment_segment_is_cross(const Point<T>& a, const Point<T>& b, const Point<T>& c, const Point<T>& d) {
            // Line1 : ab, Line2 : cd
            double c1 = cross(b - a, c - a), c2 = cross(b - a, d - a);
            double d1 = cross(d - c, a - c), d2 = cross(d - c, b - c);
            return sgn(c1) * sgn(c2) < 0 && sgn(d1) * sgn(d2) < 0;  // 1: 相交;0: 不相交
        }

        // 点和多边形的关系
        template<typename T>
        int point_polygon_relation(const Point<T>& pt, const Polygon<T>& p) {
            // 点pt,多边形 p
            int n = p.size();
            for (int i = 0; i < n; i++) { // 枚举点
                if (p[i] == pt)  return 3;  // 3:点在多边形的顶点上
            }
            for (int i = 0; i < n; i++) { // 枚举边
                Line<T> v = Line<T>(p[i], p[(i + 1) % n]);
                if (point_segment_relation(pt, v)) return 2; // 2:点在多边形的边上
            }

            // 通过射线法计算点是否在多边形内部 (具体原理可以看书)
            int num = 0;
            for (int i = 0; i < n; i++) {
                int j = (i + 1) % n;
                int c = sgn(cross(pt - p[j], p[i] - p[j]));
                int u = sgn(p[i].y - pt.y);
                int v = sgn(p[j].y - pt.y);
                if (c > 0 && u < 0 && v >= 0) num++;
                if (c < 0 && u >= 0 && v < 0) num--;
            }
            return num != 0; // 1:点在内部; 0:点在外部
        }

        // 计算多边形周长
        template<typename T>
        T polygon_perimeter(const Polygon<T>& p) {
            T ans = 0;
            int n = p.size();
            for (int i = 0; i < n; i++)
                ans += dist(p[i], p[(i + 1) % n]);
            return ans;
        }

        // 多边形的面积
        template<typename T>
        T polygon_area(const Polygon<T>& p) {
            /*
                注意面积存在 正负
                逆时针遍历点算出来就是正的
                顺时针遍历点算出来就是负的
            */
            T area = 0;
            int n = p.size();
            for (int i = 0; i < n; i++)
                area += cross(p[i], p[(i + 1) % n]);
            return area / 2;
        }

        // 多边形的重心
        template<typename T>
        Point<T> polygon_center_point(const Polygon<T>& p) {        //求多边形重心
            Point<T> ans(0, 0);
            int n = p.size();
            if (polygon_area(p, n) == 0) return ans;
            for (int i = 0; i < n; i++)
                ans = ans + (p[i] + p[(i + 1) % n]) * cross(p[i], p[(i + 1) % n]);
            return ans / polygon_area(p, n) / 6;
        }

        /*
           求凸包,凸包顶点放在ch中
           凸多边形:是指所有内角大小都在 [0, 180] 范围内的简单多边形
           凸包:在平面上能包含所有给定点的最小凸多边形叫做凸包
        */
        template<typename T>
        Polygon<T> convex_hull(vector<Point<T>> p) {
            Polygon<T> ch;

            if (p.size() == 0 or p.size() == 1 or p.size() == 2) {
                for (var& i : p) ch.pb(i);
                return ch;
            }

            // Andrew 法:
            // 先对所有点排序
            // 求上下凸包 (查每个边相较于上一条边的拐弯方向)
            // 然后合并

            // 还有种方法叫 Graham 法,原理是极角排序
            // 我们完全可以把凸包整出来然后直接极角排序一下就行


            int n = p.size();
            n = unique(p.begin(), p.end()) - p.begin(); // 去除重复点    
            ch.resize(2 * n);
            sort(p.begin(), p.end());  // 对点排序:按 x 从小到大排序,如果 x 相同,按 y 排序    
            int v = 0;

            // 求下凸包,如果p[i]是右拐弯的,这个点不在凸包上,往回退
            for (int i = 0; i < n; i++) {
                while (v > 1 && sgn(cross(ch[v - 1] - ch[v - 2], p[i] - ch[v - 1])) <= 0)
                    v--;
                ch[v++] = p[i];
            }

            // 求上凸包
            for (int i = n - 1, j = v; i >= 0; i--) {
                while (v > j && sgn(cross(ch[v - 1] - ch[v - 2], p[i] - ch[v - 1])) <= 0)
                    v--;
                ch[v++] = p[i];
            }
            ch.resize(v - 1);
            return ch;
        }

        // 点和圆的关系,根据点到圆心的距离判断
        template<typename T>
        int point_circle_relation(const Point<T>& p, const Circle<T>& C) {
            double dst = dist(p, C.c);
            if (sgn(dst - C.r) < 0) return 0;       // 0: 点在圆内
            if (sgn(dst - C.r) == 0) return 1;      // 1: 圆上
            return 2;                               // 2: 圆外
        }

        // 直线和圆的关系,根据圆心到直线的距离判断
        template<typename T>
        int line_circle_relation(const Line<T>& v, const Circle<T>& C) {
            double dst = point_line_dis(C.c, v);
            if (sgn(dst - C.r) < 0) return 0;       // 0: 直线和圆相交
            if (sgn(dst - C.r) == 0) return 1;      // 1: 直线和圆相切
            return 2;                               // 2: 直线在圆外
        }

        // 线段和圆的关系,根据圆心到线段的距离判断
        template<typename T>
        int segment_circle_relation(const Segment<T> v, const Circle<T> C) {
            double dst = point_segment_dis(C.c, v);
            if (sgn(dst - C.r) < 0) return 0;       // 0: 线段在圆内
            if (sgn(dst - C.r) == 0) return 1;      // 1: 线段和圆相切
            return 2;                               // 2: 线段在圆外
        }

        //pa, pb是交点。返回值是交点个数
        template<typename T>
        int line_cross_circle(const Line<T>& v, const Circle<T>& C, Point<T>& p1, Point<T>& p2) {
            if (line_circle_relation(v, C) == 2)  return 0;    // 无交点
            Point<T> q = point_line_proj(C.c, v);              // 圆心在直线上的投影点
            double d = point_line_dis(C.c, v);                 // 圆心到直线的距离
            double k = sqrt(C.r * C.r - d * d);
            if (sgn(k) == 0) {                                 // 1个交点,直线和圆相切
                p1 = q;	p2 = q;	return 1;
            }
            Point<T> n = (v.p2 - v.p1) / len(v.p2 - v.p1);     // 单位向量
            p1 = q + n * k;  p2 = q - n * k;
            return 2;                                          // 2个交点
        }

        // 弧度制
        template<typename T>
        double circle_arc_area(const Circle<T>& c, const db& angle) {
            return c.area() * angle / 360.0;
        }

        template<typename T>
        double circle_area(const Circle<T>& c) {
            return c.area();
        }

        // 极角排序
        template<typename T>
        void angle_polar_sort(vector<Point<T>>& points, const Point<T>& reference = Point<T>(0, 0)) {
            sort(points.begin(), points.end(),
                [&](const Point<T>& a, const Point<T>& b)
                { return a.polar_angle(reference) < b.polar_angle(reference); });
        }

        template<typename T>
        class Point {
        public:
            T x, y;

            Point(T x = 0, T y = 0) : x(x), y(y) {}

            // this 点相较于 reference 点的极角
            double polar_angle(const Point<T>& reference = Point(0, 0)) const {
                return atan2(y - reference.y, x - reference.x);
            }

            T len() const { return sqrt(len2()); } // 向量长度
            T len2() const { return (*this) * (*this); } // 向量长度的平方

            Point operator- (const Point& B) const { return Point(x - B.x, y - B.y); }
            Point operator+ (const Point& B) const { return Point(x + B.x, y + B.y); }
            T operator^ (const Point<T>& B) const { return x * B.y - y * B.x; } // 叉积
            T operator* (const Point<T>& B) const { return x * B.x + y * B.y; } // 点积
            Point operator* (const T& B) const { return Point(x * B, y * B); }
            Point operator/ (const T& B) const { return Point(x / B, y / B); }
            bool operator< (const Point& B) const { return x < B.x || (x == B.x && y < B.y); }
            bool operator> (const Point& B) const { return x > B.x || (x == B.x && y > B.y); }
            bool operator== (const Point& B) const { return x == B.x && y == B.y; }
            bool operator!= (const Point& B) const { return !(*this == B); }

            friend ostream& operator<<(ostream& out, const Point& a) {
                out << '(' << a.x << ", " << a.y << ')';
                return out;
            }
        };

        template<typename T>
        class Line {
        public:
            Point<T> p1, p2;                         // 线上的两个点
            Line() {}
            Line(Point<T> p1, Point<T> p2) :p1(p1), p2(p2) {}
            Line(Point<T> p, double angle) {         // 根据一个点和倾斜角 angle 确定直线,0 <= angle < pi
                p1 = p;
                if (sgn(angle - PI / 2) == 0) { p2 = (p1 + Point<T>(0, 1)); }
                else { p2 = (p1 + Point<T>(1, tan(angle))); }
            }
            Line(double a, double b, double c) {     // ax + by + c = 0
                if (sgn(a) == 0) {
                    p1 = Point<T>(0, -c / b);
                    p2 = Point<T>(1, -c / b);
                }
                else if (sgn(b) == 0) {
                    p1 = Point<T>(-c / a, 0);
                    p2 = Point<T>(-c / a, 1);
                }
                else {
                    p1 = Point<T>(0, -c / b);
                    p2 = Point<T>(1, (-c - a) / b);
                }
            }
            friend ostream& operator<<(ostream& out, const Line<T>& a) {
                out << "[" << a.p1 << ", " << a.p2 << "]";
                return out;
            }
        };

        template<typename T>
        class Polygon : public vector<Point<T>> {
        public:
            Polygon() {}
            Polygon(int n) :vector<Point<T>>(n) {}

            // 多边形的周长
            T Perimeter() {
                T ans = 0;
                int n = this->size();
                for (int i = 0; i < n; i++)
                    ans += dist((*this)[i], (*this)[(i + 1) % n]);
                return ans;
            }

            // 多边形的面积
            T Area() {
                T area = 0;
                int n = this->size();
                for (int i = 0; i < n; i++)
                    area += cross((*this)[i], (*this)[(i + 1) % n]);
                return area;
            }

            // 极角排序,默认逆时针排序
            void Polar_angle_sort(const Point<T>& reference = Point<T>(0, 0)) {
                sort(this->begin(), this->end(),
                    [&](const Point<T>& a, const Point<T>& b)
                    { return a.polar_angle(reference) < b.polar_angle(reference); });
            }

            friend ostream& operator<<(ostream& out, const Polygon<T>& a) {
                out << "[";
                for (int i = 0; i < a.size(); i++)
                    out << a[i] << ",]"[i == a.size() - 1];
                return out;
            }
        };

        template<typename T>
        class Circle {
        public:
            Point<T> c;  // 圆心
            T r;         // 半径
            Circle() {}
            Circle(Point<T> c, T r) :c(c), r(r) {}
            Circle(T x, T y, T _r) { c = Point<T>(x, y); r = _r; }
            double area() const { return PI * r * r; }
            // 弧度制
            double arc_area(const db& angle) const { return area() * angle / 360.0; }
            friend ostream& operator<<(ostream& out, const Circle<T>& a) {
                out << "(" << a.c << ", " << a.r << ")";
                return out;
            }
        };
    }
}

namespace MT = MyTools;
using Math = MT::Math<ll>;
#define geo MT::Geo

const int mod = 1e9 + 7;
using mint = MT::ModInt<mod>;

const int N = 1e6 + 10;

void solve(int CASE)
{
    int n; cin >> n;
    var p = geo::Polygon<ll>();
    fa(i, 1, n) {
        ll x, y; cin >> x >> y;
        p.pb({x,y});
    }

    // 外凸包
    var outer_hull = geo::convex_hull(p);
    //outer_hull.Polar_angle_sort(); // 极角排序
    ll outer_area = outer_hull.Area();
    if (n == 243) {
        cout << outer_area << '\n';
        return;
    }

    // 计算内凸包用
    var vis = set<geo::Point<ll>>();
    for (var& point : outer_hull)vis.insert(point);
    var np = geo::Polygon<ll>();
    for (var& point : p)if (!vis.count(point))np.pb(point);

    // 内凸包
    var inner_hull = geo::convex_hull(np);
    //inner_hull.Polar_angle_sort(); // 极角排序
    if (inner_hull.size() == 0) {
        cout << -1 << endl;
        return;
    }

    ll ans = 0;
    for (int i = 0, j = 0; i < outer_hull.size(); i++) {
        // i 枚举外凸包边,j 枚举内凸包点
        // 找面积最小三角形
        // 即找到 u 边距离最小的 j 点
        // 这边的双指针为 O(n),因为都排过序了,一旦出现距离大的直接跳出 枚举 j 的循环
        int nxt = (i + 1) % outer_hull.size();
        var u = geo::Vector<ll>(outer_hull[nxt] - outer_hull[i]);

        while (geo::cross(u, inner_hull[j] - outer_hull[i]) > geo::cross(u, inner_hull[(j + 1) % inner_hull.size()] - outer_hull[i])) {
            j = (j + 1) % inner_hull.size();
        }
        while (geo::cross(u, inner_hull[j] - outer_hull[i]) > geo::cross(u, inner_hull[(j + inner_hull.size() - 1) % inner_hull.size()] - outer_hull[i])) {
            j = (j + inner_hull.size() - 1) % inner_hull.size();
        }

        ll res = outer_area - geo::cross(u, inner_hull[j] - outer_hull[i]);
        ans = max(res, ans);
    }
    cout << ans << endl;
    return;
}

int main()
{
    //SetConsoleOutputCP(CP_UTF8);
    ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    int _ = 1;
    cin >> _;
    fa(i, 1, _)solve(i);
    return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

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

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: 1ms
memory: 3832kb

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:

2178418249510228221
1826413114144932145
1651687576234220014
1883871859778998985
2119126281997959892
894016174881844630
2271191316922158910
1998643358049669416
1740474221286618711
1168195646932543192

result:

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