QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#695970#9520. Concave Hullucup-team3294AC ✓153ms22012kbC++2025.8kb2024-10-31 21:12:112024-10-31 21:12:16

Judging History

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

  • [2024-10-31 21:12:16]
  • 评测
  • 测评结果:AC
  • 用时:153ms
  • 内存:22012kb
  • [2024-10-31 21:12:11]
  • 提交

answer

#include <bits/stdc++.h>
using namespace std;
typedef long double ldb;
#define int long long
#define _sign(x) ((x)>eps?1:((x)<-eps?2:0))  //若x>eps return 1 若x<-eps  return 2 否则返回0
const long double pi=acos(-1);
const int INF=0x3f3f3f3f;
const long double DINF=1e18,eps=1e-3;
#define endl '\n'
typedef long long ll;
int T=1;
struct Point
{
    long double x,y,z=0;
    Point(long double x=0,long double y=0):x(x),y(y){} //具体来说,这个构造函数带有两个参数 x 和 y,它们的默认值分别为 0。在这种情况下,如果您创建一个 Point 对象而没有提供任何参数,它将被初始化为 (0, 0)。
    long double abs() { return sqrt(abs2()); }
    long double abs2() { return x * x + y * y; }

};  
int sgn(long double x)
{
    if(fabs(x)<eps)
    {
        return 0;
    }
    if(x<0) return -1;
    return 1;
}
// !注意区分点和向量
typedef Point Vector;
// 向量平移之后还是那个向量,所以只需要原点和向量的终点即可
// !向量 + 向量 = 向量,点 + 向量 = 向量
Vector operator + (Vector A, Vector B){return Vector(A.x + B.x, A.y + B.y);}
// !点 - 点 = 向量(向量BC = C - B)
// 点+向量=向量
Vector operator - (Point A, Point B){return Vector(A.x - B.x, A.y - B.y);}
// !向量 * 数 = 向量
Vector operator * (Vector A, long double p){return Vector(A.x * p, A.y * p);}
// !向量 / 数= 向量
Vector operator / (Vector A, long double p){return Vector(A.x / p, A.y / p);}
// !点/向量的比较函数
bool operator < (const Point& a, const Point& b) {return sgn(a.x - b.x)<0 || (sgn(a.x - b.x)==0 & sgn(a.y - b.y)<0);}
// !求极角/ 在极坐标系中,平面上任何一点到极点的连线和极轴的夹角叫做极角。
// 单位弧度rad
long double Polar_angle(Vector A){return atan2(A.y, A.x);}
// !三态函数sgn用于判断相等,减少精度误差问题

bool cmpp(Point x,Point y,Point tttt)  
{
    return  (x-tttt).abs2()<(y-tttt).abs2();  //tttt是一个点,排序比较函数是x到tttt的欧几里得距离大小来比较
}
// 重载等于运算符
bool operator == (const Point& a, const Point& b){return !sgn(a.x - b.x) && !sgn(a.y - b.y);}
// !点积(满足交换律)
long double Dot(Vector A, Vector B){return A.x * B.x + A.y * B.y;}
// !向量的叉积(不满足交换律)
// 等于两向量有向面积的二倍(从v的方向看,w在左边,叉积>0,w在右边,叉积<0,共线,叉积=0)
// cross(x, y) = -cross(y, x)
// cross(x, y) : xAyB - xByA
long double Cross(Vector A, Vector B){return A.x * B.y - B.x * A.y;}  //二维叉积
long double dot_product(const Point &a, const Point &b) //三维点积
{
    return a.x * b.x + a.y * b.y + a.z * b.z;
}
Vector cross_product(Vector a, Vector b)  //三维叉积,返回的是向量
{
    Vector ans;
    ans.x = a.y * b.z - a.z * b.y;
    ans.y = a.z * b.x - a.x * b.z;
   ans.z = a.x * b.y - a.y * b.x;
    return ans;
}
bool ToLeftTest(Point a, Point b, Point c)  //判断向量bc是不是向量ab的逆时针方向,也可以看成一个点c是否在向量ab左边
{
    return Cross(b - a, c - b) > 0;
}
long double Length(Vector A){return sqrt(Dot(A, A));} //求向量模长
long double Angle(Vector A, Vector B){return acos(Dot(A, B) / Length(A) / Length(B));} //返回弧度制下的夹角
// !三个点确定两个向量,(交点为A的两个向量AB和AC)然后求这两个向量的叉积(叉乘)
long double Area2(Point A, Point B, Point C){return Cross(B - A, C - A);}
// !向量的单位法线实际上就是将该向量向左旋转90°
// 因为是单位法线所以长度归一化调用前请确保A不是零向量
Vector Normal(Vector A) //Normal表示逆时针90度的单位法向量
{
    long double L = Length(A);
    return Vector(-A.y / L, A.x / L);
}
inline Vector Format(const Vector &A) //归成单位向量
{
    long double L = Length(A);
    return Vector(A.x / L,A.y / L);
}
// !一个向量旋转rad弧度之后的新向量(点也行)
// !x' = xcosa - ysina, y' = xsina + ycosa
// rad:弧度 且为逆时针旋转的角
Vector Rotate(Vector A, long double rad)
{
    return Vector(A.x * cos(rad) - A.y * sin(rad), A.x * sin(rad) + A.y * cos(rad));
}
inline Point turn_PP(Point a, Point b, long double theta)
{// 【将点A绕点B顺时针旋转theta(弧度)】  //注意是顺时针
    long double x = (a.x-b.x) * cos(theta) + (a.y-b.y) * sin(theta) + b.x;
    long double y = - (a.x-b.x) * sin(theta) + (a.y-b.y) * cos(theta) + b.y;
    return Point(x,y);
}
///线
struct Line
{// 直线定义
    Vector v;
    Point p;
    Line(Vector v, Point p):v(v), p(p) {}
    Point get_point_in_line(long double t)
    {// 返回直线上一点P = p + ( v)*t
        return p + (v)*t;
     }
};
//Line a(v,p);
// 点和直线关系
// 1 在左侧
// -1 在右侧
// 0 在直线上 / 直线上两点s和e
// A, B:直线上一点,C:待判断关系的点
int relation_point(Point A, Point B, Point C)
{
    // 1 left -1 right 0 in
    int c = sgn(Cross((B - A), (C - A)));
    if(c < 0) return 1;
    else if(c > 0) return -1;
    return 0;
}
long double xmult(Point p1,Point p2,Point p0)  //返回向量p0p1,p0p2的叉积
{
    return (p1.x-p0.x)*(p2.y-p0.y)-(p2.x-p0.x)*(p1.y-p0.y);
}
/// 调用前要确保两直线p + tv 和 Q + tw之间有唯一交点,当且仅当Corss(v, w) ! 0;(t是参数)
Point Get_line_intersection(Point P,Vector v,Point Q,Vector w)
{
    Vector u = P - Q;
    long  double t = (ldb)Cross(w, u) / (ldb)Cross(v, w);
    return P + v * t;
}
long double Dis_point_to_point(Point a,Point b)
{
    return sqrt((a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y));
}
long double Dis_point_to_point2(Point a,Point b)
{
    return ((a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y));
}
// !直线的参数式 直线 AB:A + tv(v为向量AB, t为参数)
long double Distance_point_to_line(Point P, Point A, Point B)  //P到ab直线的距离
{
    Vector v1 = B - A, v2 = P - A;
    return fabs(Cross(v1, v2) / Length(v1));// 如果不取绝对值,那么得到的是有向距离
}
// 垂线距离或者PA或者PB距离
long double Distance_point_to_segment(Point P, Point A, Point B)  //p到ab线段的距离
{
    if(A == B) return Length(P - A);// (如果重合那么就是两个点之间的距离,直接转成向量求距离即可)
    Vector v1 = B - A, v2 = P - A, v3 = P - B;
    if(sgn(Dot(v1, v2)) < 0) return Length(v2);// A点左边
    if(sgn(Dot(v1, v3)) > 0)return Length(v3);// B点右边
    return fabs(Cross(v1, v2) / Length(v1));// 垂线的距离
}
// !点在直线上的投影
// 点积满足分配率:两直线垂直,点积为0,向量v,Q = A + t0v,
// 点P,v与直线PQ垂直:  
// Dot(v, p - (A + t0v)) = 0 -> Dot(v, P - A) - t0 * Dot(v, v) = 0;
Point Get_line_projection(Point P, Point A, Point B) //求点p在ab直线上的投影点
{
    Vector v = B - A;
    return A + v * (Dot(v, P - A) / Dot(v, v));
}
inline Point FootPoint(Point p, Point a, Point b)  //投影点和垂足好像没有什么区别
{// 【点P到直线AB的垂足】
    Vector x = p - a, y = p - b, z = b - a;
    long double len1 = Dot(x, z) / Length(z), len2 = - 1.0 * Dot(y, z) / Length(z);// 分别计算AP,BP在AB,BA上的投影
    return a + z * (len1 / (len1 + len2));// 点A加上向量AF
}
inline Point Symmetry_PL(Point p, Point a, Point b)
{
    // 【点P关于直线AB的对称点】
    return p + (FootPoint(p, a, b) - p) * 2;
    // 实际上就是求垂足之后延长一倍得到的向量,与原来的点加起来就行了
}
bool OnSegment(Point p, Point a1, Point a2)  //点是否在线段上
{
    return sgn(Cross(a1-p, a2-p)) == 0 & sgn(Dot(a1-p, a2-p)) <= 0;
}
bool segment_proper_intersection(Point a1, Point a2, Point b1, Point b2) //线段是否相交 不含端点
{
    long double c1 = Cross(a2 - a1, b1 - a1), c2 = Cross(a2 - a1, b2 - a1);
    long double c3 = Cross(b2 - b1, a1 - b1), c4 = Cross(b2 - b1, a2 - b1);
    return sgn(c1) * sgn(c2) < 0 && sgn(c3) * sgn(c4) < 0;
    
}
bool Segment_proper_intersection(Point a1, Point a2, Point b1, Point b2)// 线段是否相交 包含端点相交
{

    long double c1 = Cross(a2-a1, b1-a1), c2 = Cross(a2-a1, b2-a1);
    long double c3 = Cross(b2-b1, a1-b1), c4 = Cross(b2-b1, a2-b1);
    // if判断控制是否允许线段在端点处相交,根据需要添加
    if(!sgn(c1) || !sgn(c2) || !sgn(c3) || !sgn(c4))
    {
        bool f1 = OnSegment(b1, a1, a2);
        bool f2 = OnSegment(b2, a1, a2);
        bool f3 = OnSegment(a1, b1, b2);
        bool f4 = OnSegment(a2, b1, b2);
        bool f = (f1|f2|f3|f4);
        return f;
    }
    return (sgn(c1)*sgn(c2) < 0 && sgn(c3)*sgn(c4) < 0);
}
bool on_segment(Point P, Point a1, Point a2)  //判断点是否在线段上(不含端点)
{
    return sgn(Cross(a1 - P, a2 - P)) == 0 & sgn(Dot(a1 - P, a2 - P)) < 0;
}
Point segment_intersection(Point p1,Point p2,Point p3,Point p4)  //默认有交点
{
    if(relation_point(p1,p2,p3)==0) return p3;
    else if(relation_point(p1,p2,p4)==0) return p4;
    else if(relation_point(p3,p4,p1)==0) return p1;
    else if(relation_point(p3,p4,p2)==0) return p2;
    long double t=Cross(p1-p3,p3-p4)/Cross(p1-p2,p3-p4);
    long double s=Cross(p1-p3,p1-p2)/Cross(p1-p2,p3-p4);
    Point ans;
    ans.x=p1.x+t*(p2.x-p1.x);  //x=p3.x+s*(p4.x-p3.x);
    ans.y=p1.y+t*(p2.y-p1.y);  //y=p3.y+s*(p4.y-p4.y);
    return ans;

}
long double Distance_segment_to_segment(Point p1,Point p2,Point p3, Point p4)
{
    if(Segment_proper_intersection(p1,p2,p3,p4)) return 0.00;
    long double ans=1e9;
    ans=min(ans,Distance_point_to_segment(p3,p1,p2));
    ans=min(ans,Distance_point_to_segment(p4,p1,p2));
    ans=min(ans,Distance_point_to_segment(p1,p3,p4));
    ans=min(ans,Distance_point_to_segment(p2,p3,p4));
    return ans;
}
////多边形
//求多边形面积
int polyg_on_area(vector<Point> &cnt,int n)  //n边形
{
    int area=0;
    for(int i=1;i<=n-2;i++)
    {
        area+=(int)Cross(cnt[i]-cnt[0],cnt[i+1]-cnt[0]);
    }
    return area;

}
int is_point_in_polygon(Point p,vector<Point> poly)  //判断点是否在多边形内部,是返回1,不是返回0,在多边形上返回-1
{
    int wn=0;
    int n=poly.size();
    for(int i=0;i<n;i++)
    {
        if(OnSegment(p,poly[i],poly[(i+1)%n])) return -1;
        int k=sgn(Cross(poly[(i+1)%n]-poly[i],p-poly[i]));
        int d1=sgn(poly[i].y-p.y);
        int d2=sgn(poly[(i+1)%n].y-p.y);
        if(k>0&&d1<=0&&d2>0) wn++;
        if(k<0&&d2<=0&&d1>0) wn--;
    }
    if(wn!=0) return 1;
    return 0;
}
int is_convex(int n,vector<Point> p)  //判断是否为凸多边形,顶点按顺时针或者逆时针给出,允许邻边共线
{
    int s[3]={1,1,1};
    for(int i=0;i<n&&(s[1]|s[2]);i++)
    {
        s[_sign(xmult(p[(i+1)%n],p[(i+2)%n],p[i]))]=0;
    }
    return s[1]|s[2];

}
int is_convex_v2(int n,vector<Point> p) //不允许邻边共线
{
    int s[3]={1,1,1};
    for(int i=0;i<n&&(s[1]|s[2])&&s[0];i++)
    {
        s[_sign(xmult(p[(i+1)%n],p[(i+2)%n],p[i]))]=0;
    }
    return s[0]&&s[1]|s[2];
}
Point barycenter(int n,vector<Point> p)  //逆时针给点
{
    Point ans;
    ans.x=0;
    ans.y=0;
    long double ss=0;
    for(int i=1;i<n-1;i++)
    {
        if(fabs(xmult(p[i],p[i+1],p[0]))>eps)  //判断三点不共线
        {
            long double s=xmult(p[i],p[i+1],p[0]); //即使是非凸四边形,面积最后也会消掉,所以不用加绝对值
            ans.x+=(p[0].x+p[i].x+p[i+1].x)*s;
            ans.y+=(p[0].y+p[i].y+p[i+1].y)*s;
            ss+=s;
        }
    }
    if(fabs(ss)>eps)
    {
        ans.x/=ss;
        ans.x/=3;
        ans.y/=ss;
        ans.y/=3;
    }
    return ans;
}
int segment_isin_polygon(Point l1,Point l2,int n,vector<Point> p)//判断线段是否在多边形内(顶点在边上也算在多边形内)
{
    if(!is_point_in_polygon(l1,p)||!is_point_in_polygon(l2,p)) return 0;
    vector<Point> t;
    for(int i=0;i<n;i++)
    {
        if(segment_proper_intersection(l1,l2,p[i],p[(i+1)%n])) return 0;
        else if(OnSegment(l1,p[i],p[(i+1)%n])) t.push_back(l1);
        else if(OnSegment(l2,p[i],p[(i+1)%n])) t.push_back(l2);
        else if(OnSegment(p[i],l1,l2)) t.push_back(p[i]);
    }
    sort(t.begin(),t.end());  //或者暴力枚举每两个点
    for(int i=0;i<t.size()-1;i++)
    {
        Point tt;
        tt.x=(t[i].x+t[i+1].x)/2;
        tt.y=(t[i].y+t[i+1].y)/2;
        if(!is_point_in_polygon(tt,p)) return 0;
    }
    return 1;

}
struct Circle
{
    Point c;
    long double r;
    Circle(Point c=Point(),long double r=0):c(c),r(r){} //Circle c
     //若要访问圆心  c.c.x   c.c.y
    inline Point point(long double a) //通过圆心角求坐标
    {
        return Point(c.x+cos(a)*r,c.y+sin(a)*r);
    }
};

int get_line_circle_intersection(Line L,Circle C,long double &t1,long double &t2,vector<Point>& sol)
{
    long double a = L.v.x, b = L.p.x - C.c.x, c = L.v.y, d = L.p.y - C.c.y;
    long double e = a*a + c*c, f = 2*(a*b + c*d), g = b*b + d*d - C.r*C.r;
    long double delta1 = f*f - 4*e*g;// 判别式
    if(sgn(delta1) < 0)// 相离
    return 0;
    if(sgn(delta1) == 0){// 相切
    t1 = -f /(2*e);
    t2 = -f /(2*e);
    sol.push_back(L.get_point_in_line(t1));// sol存放交点本身
    return 1;
     }
      // 相交
    t1 = (-f - sqrt(delta1))/(2*e);
    sol.push_back(L.get_point_in_line(t1));
    t2 = (-f + sqrt(delta1))/(2*e);
    sol.push_back(L.get_point_in_line(t2));
    return 2;
}
int get_circle_circle_intersection(Circle c1,Circle c2,vector<Point> &sol)
{
    long double d = Length(c1.c - c2.c);
    if(sgn(d) == 0)
    {
        if(sgn(c1.r - c2.r) == 0)return -1;// 两圆重合
        return 0;
     }
    if(sgn(c1.r + c2.r - d) < 0)return 0;// 相离
    if(sgn(fabs(c1.r - c2.r) - d) > 0)return 0;// 在另一个圆的内部
    long double a = atan2((c2.c - c1.c).y,(c2.c-c1.c).x);// 向量c1c2的极角
    //cout<<a<<"dd"<<endl;
    long double da = acos((c1.r * c1.r + d * d - c2.r * c2.r) / (2 * c1.r * d));
    // c1c2到c1p1的角
    Point p1 = c1.point(a - da), p2 = c1.point(a + da);
    sol.push_back(p1);
    if(p1 == p2)return 1;
    sol.push_back(p2);
    return 2;
}
// 过点p到圆c的切线,v[i]是第i条切线, 返回切线的条数
int get_tangents(Point p, Circle C, vector<Vector> &k)
{
    Vector u = C.c - p;
    long double dist = Length(u);
    if(dist < C.r)return 0;// 点在内部,没有切线
    else if(sgn(dist - C.r) == 0)
    {// p在圆上,只有一条切线
        k.push_back(Rotate(u,pi/2));
        //v[0] = Rotate(u, pi / 2);// 切线就是垂直嘛
        return 1;
     }
    else 
    {// 否则是两条切线
        long double ang = asin(C.r / dist);
        k.push_back(Rotate(u,-ang));
        k.push_back(Rotate(u,+ang));
       // v[0] = Rotate(u, - ang);
       // v[1] = Rotate(u, +ang);
        return 2;
     }
}
int get_tangents_point(Point p,Circle c,vector<Point> &k)
{
    vector<Vector> ans;
    int cnt=get_tangents(p,c,ans);
    if(cnt==0) return 0;  //点在圆内
    if(cnt==1)
    {
        Line l(ans[0],p);
       long double t1,t2;
       int u=get_line_circle_intersection(l,c,t1,t2,k);
       // for(int i=0;i<=1;i++)
       // {
       //  std::cout << std::fixed << std::setprecision(8) <<kk[0].x<<' '<<kk[0].y<<endl;
       // }
       return 1;
    }
    else
    {
        Line l1(ans[0],p);
        Line l2(ans[1],p);
        vector<Point> kk;
        long double t1,t2;
        int u=get_line_circle_intersection(l1,c,t1,t2,k);
         u=get_line_circle_intersection(l2,c,t1,t2,k);
         sort(k.begin(),k.end());
         // for(int i=0;i<=1;i++)
         // {
         //    std::cout << std::fixed << std::setprecision(8) <<kk[i].x<<' '<<kk[i].y<<endl;
         // }
         return 2;
    }
}
inline Circle getcircle(Point A,Point B,Point C)  //求外接圆
{// 【三点确定一圆】向量垂直平分线法
    Point P1=(A+B)*0.5,P2=(A+C)*0.5;
    Point O=Get_line_intersection(P1,Normal(B-A),P2,Normal(C-A));
    return Circle(O,Length(A-O));
}
Circle NeiJieYuan(Point p1,Point p2,Point p3)  //求内接圆
{
   long double a=Length(p2-p3);
    long double b=Length(p3-p1);
    long double c=Length(p1-p2);
    Point p=(p1*a+p2*b+p3*c)/(a+b+c);
    return Circle(p,Distance_point_to_line(p,p1,p2));
}
Circle WaiJieYuan(Point p1,Point p2,Point p3)  //外接圆
{
    double Bx=p2.x-p1.x,By=p2.y-p1.y;
    double Cx=p3.x-p1.x,Cy=p3.y-p1.y;
    double D=2*(Bx*Cy-By*Cx);
    double ansx=(Cy*(Bx*Bx+By*By)-By*(Cx*Cx+Cy*Cy))/D+p1.x;
    double ansy=(Bx*(Cx*Cx+Cy*Cy)-Cx*(Bx*Bx+By*By))/D+p1.y;
    Point p(ansx,ansy);
    return Circle(p,Length(p1-p));
}
// 返回切线的条数,-1表示无穷条切线
// /a[i]和b[i] 分别是第i条切线在圆A和圆B上的切点
int get_circletangents(Circle A, Circle B, vector<Point> &a, vector<Point>&b)
{
    int cnt = 0;
    if(A.r < B.r)swap(A, B), swap(a, b);  //注意这里交换了,如果A.r<B.r  那么b里面存a的切点
    int d2 = (A.c.x - B.c.x) * (A.c.x - B.c.x) + (A.c.y - B.c.y) * (A.c.y - B.c.y);
    int rdiff = A.r - B.r;
    int rsum = A.r + B.r;
    if(d2 < rdiff * rdiff)return 0;// 内含
    double base = atan2(B.c.y - A.c.y, B.c.x - A.c.x);
    if(d2 == 0 & A.r == B.r)return -1;// 无限多条切线
    if(d2 == rdiff * rdiff)
    {// 内切,1条切线
        a.push_back( A.point(base));
        b.push_back( B.point(base)); cnt ++ ;
        return 1;
     }
    // 有外共切线
    double ang = acos((A.r - B.r) / sqrt(d2));
    a.push_back( A.point(base + ang));b.push_back( B.point(base + ang));cnt ++ ;
    a.push_back(A.point(base - ang));b.push_back(B.point(base - ang));cnt ++ ;
    if(d2 == rsum * rsum)
    {   // 一条内公切线
        a.push_back(A.point(base));b.push_back(B.point(pi + base)); cnt ++ ;
     }
    else if(d2 > rsum * rsum)
    {   // 两条内公切线
        double ang = acos((A.r + B.r) / sqrt(d2));
        a.push_back(A.point(base + ang)); b.push_back(B.point(pi + base + ang)); cnt ++ ;
        a.push_back(A.point(base - ang)); b.push_back(B.point(pi + base - ang)); cnt ++ ;
    }
    return cnt;
}
//通过计算两个圆相交所构成的两个扇形面积和减去其构成的筝形的面积
long double AreaOfOverlap(Point c1, long double r1, Point c2, long double r2)  //求两圆相交面积
{
    long double d = Length(c1 - c2);
    //cout<<c2.x<<endl;
    if(r1 + r2 < d + eps)
    return 0.0;
    if(d < fabs(r1 - r2) + eps)
    {
        long double r = min(r1, r2);
        return pi*r*r;
     }
    long double x = (d*d + r1*r1 - r2*r2)/(2.0*d);
    long double p = (r1 + r2 + d)/2.0;
    long double t1 = acos(x/r1);
    long double t2 = acos((d - x)/r2);
    long double s1 = r1*r1*t1;
    long double s2 = r2*r2*t2;
    long double s3 = 2*sqrt(p*(p - r1)*(p - r2)*(p - d));
    return s1 + s2 - s3;
}
int grid_onedge(int n,vector<Point> p)  //返回多边形边上的网格点个数  s=in+(edge/2)-1  //面积s可以通过三角剖分叉积算
{
    int ret=0;
    for (int i=0;i<n;i++ )
    ret+=__gcd(abs((int)p[i].x-(int)p[(i+1)%n].x),abs((int)p[i].y-(int)p[(i+1)%n].y));
    return ret;
}
bool argcmp(const Point &a,const Point &b)  //下半平面<原点<x正半轴<上半平面<x负半轴
{
    auto quad=[](const Point &a)
    {
        if(a.y<-eps) return 1;  //在下半平面
        if(a.y>eps) return 4; //在上半平面
        if(a.x<-eps) return 5;//在负x轴
        if(a.x>eps) return 3;//在正x轴
        return 2;//在原点

    };
    int qa=quad(a),qb=quad(b);
    if(qa!=qb) return qa<qb;
    int t=(int)Cross(a,b);
    if(abs(t)<=eps) return a.x*a.x+a.y*a.y<b.x*b.x+b.y*b.y-eps;  //如果t等0,说明他们的极角一样,这时候按照长度比
    return t>eps;

}
// 计算凸包,输入点数组p,个数为p输出点数组ch,函数返回凸包顶点个数。
// 输入不能有重复的点,函数执行完后的输入点的顺序将被破坏(因为要排序,可以加一个数组存原来的id)
// 如果不希望在凸包边上有输入点,把两个< 改成<=即可
int ConvexHull(vector<Point> &p, int n, vector<Point> &ch)
{
    sort(p.begin(), p.begin() + n);
    int m = 0;
    for(int i = 0; i < n; ++ i)
    {// 下凸包
    // 如果叉积<= 0说明新边斜率小说明已经不是凸包边了,赶紧踢走
        while(m > 1 && Cross(ch[m - 1] - ch[m - 2], p[i] - ch[m - 2]) <=0)
        {
            m--;
            ch.pop_back();
        }
        ch.push_back(p[i]);
       // flag[i]=1;
        m++;
     }
    int k = m;
    for(int i = n - 2; i >= 0; -- i)
    {// 上凸包
        while(m > k && Cross(ch[m - 1] - ch[m - 2], p[i] - ch[m - 2]) <=0)
        {
            m--;
            ch.pop_back();
        }
        ch.push_back(p[i]);
        m++;
     }
    if(n > 1) m -- ;
    return m;
}
long double Convex_hull_diameter(vector<Point> p,int num) //返回直径平方,p必须没有三点共线的凸包
{
    if(num==2)
    {
        return (int)Dis_point_to_point2(p[0],p[1]);
        
    }
    if(num==3)
    {
        return max({(int)Dis_point_to_point2(p[0],p[1]),(int)Dis_point_to_point2(p[0],p[2]),(int)Dis_point_to_point2(p[1],p[2])});
    }
    p.push_back(p[0]);
    int pos=2;
    long double ans=-1e8;
    for(int i=0;i<p.size()-1;i++)
    {
        auto p1=p[i];
        auto p2=p[i+1];
        auto p3=p[pos];
        auto t=Area2(p1,p2,p3);
        long double maxx=t;
        int j=pos;
        while(j<p.size()-1&&Area2(p1,p2,p[j])>=maxx)
        {
            //j++;
            maxx=Area2(p1,p2,p[j]);
            ans=max({ans,Dis_point_to_point2(p1,p[j]),Dis_point_to_point2(p2,p[j])});
            j++;

        }
        pos=j-1;

    }
    return ans;

}
int is_in_convexhull(vector<Point> &p,Point t,int n) //n>=3,逆时针,要传数组指针
{
        if(t==p[0])
        {
            return 0;
        }
        if(OnSegment(t,p[0],p[1]))
        {
            return 0;
        }
        if(OnSegment(t,p[0],p[n-1]))
        {
            return 0;
        }
        if(ToLeftTest(p[0],p[n-1],t))
        {
            return 1;
        }
        if(ToLeftTest(p[1],p[0],t))
        {
            return 1;
        }
        int l=2,r=n-1;
        while(l<r)
        {
            int mid=l+r>>1;
            if(ToLeftTest(p[0],p[mid],t)) l=mid+1;
            else r=mid;
        }
        Point t1=p[l-1];
        Point t2=p[l];
        if(OnSegment(t,t1,t2))
        {
            return 0;
        }
        //cout<<t1.x<<"pa"<<t1.y<<endl;
        if(ToLeftTest(t1,t2,t))
        {
            return -1;
        }
        else return 1;
}
void solve(int u)
{
    //  long double number = 3.14159265358979323846;
    
    // // 使用流操纵器保留6位小数并输出
    // std::cout << std::fixed << std::setprecision(6) << number << std::endl;
    
   // cout<<"aaa"<<endl;
    int n;
    cin>>n;
    vector<Point> a;
    for(int i=1;i<=n;i++)
    {
        Point t;
        cin>>t.x>>t.y;
        t.z=i;
        a.push_back(t);
    }
    // if(T==7&&u==5)
    // {
    //     cout<<a[0].x<<" "<<a[0].y<<" "<<a[1].x<<" "<<a[1].y<<" "<<a[2].x<<" "<<a[2].y<<" "<<a[3].x<<" "<<a[3].y<<" "<<a[4].x<<" "<<a[4].y<<" "<<a[5].x<<" "<<a[5].y<<endl;
    //     return ;
    // }
    vector<Point> convh;
    int m=ConvexHull(a,n,convh);
    vector<Point> tt;
    set<int> se;
    for(int i=0;i<convh.size();i++)
    {
        se.insert(convh[i].z);
    }
    for(int i=0;i<a.size();i++)
    {
        if(se.count(a[i].z)==0) tt.push_back(a[i]);
    }
    vector<Point> convh1;
    int m1=ConvexHull(tt,tt.size(),convh1);
    if(m1==0)
    {
        cout<<-1<<endl;
        return ;
    }
    int ans=polyg_on_area(convh,m);
    int res=7e18;
    if(convh1.size()>1)
    convh1.pop_back();
    convh.pop_back();
    //sort(convh1.begin(),convh1.end());
   // sort(convh.begin(),convh.end());
    int idx=0;
    // for(int i=0;i<convh.size();i++)
    // {
    //     cout<<convh[i].x<<" "<<convh[i].y<<endl;
    // }
    // cout<<"aa"<<endl;
    // for(int i=0;i<convh1.size();i++)
    // {
    //     cout<<convh1[i].x<<' '<<convh1[i].y<<endl;
    // }
    // cout<<"aa"<<endl;
    // cout<<m<<"aaaaa"<<m1<<endl;
    if(m1==1)
    {
        auto t=convh1[0];
        for(int i=0;i<convh.size();i++)
        {
            res=min(res,abs((int)Cross(convh[i]-t,convh[(i+1)%m]-t)));
        }
        cout<<ans-res<<endl;
        return ;
    }
    multiset<int> see;
    int num=0;
    for(int i=0;i<convh.size();i++)
    {
        long double cnt=7e18;
        Point kk;
        auto t1=convh[i];
        auto t2=convh[(i+1)%m];
        int flag=0;
       // cnt=Distance_point_to_line(convh1[idx],t1,t2);
       // idx++;
        //idx%=m1;
        //int num=0;
        while(Distance_point_to_line(convh1[idx],t1,t2)<cnt)
        {
            //cout<<idx<<"aa"<<endl;
            num++;
            cnt=min(cnt,Distance_point_to_line(convh1[idx],t1,t2));
          //  see.insert(idx);
            kk=convh1[idx];
            idx++;
           // cout<<"aa"<<endl;
            idx%=m1;
            flag=1;
        }
        res=min(res,abs((int)Cross(t1-kk,t2-kk)));
        if(flag)
        {
            idx=(idx-1+m1)%m1;
        }
       // cout<<idx<<"aa"<<endl;

    }
    // for(int i=0;i<convh1.size();i++)
    // {
    //     auto t=convh1[i];
    //     for(int j=0;j<convh.size();j++)
    //     {
    //         res=min(res,abs((int)Cross(convh[j]-t,convh[(j+1)%m]-t)));
    //     }
    // }
     cout<<ans-res<<endl;
    
    

   
}
signed main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    cin>>T;
    //cout<<acos(-1.0)<<endl;
    for(int i=1;i<=T;i++)
    {
        solve(i);
    }
}

这程序好像有点Bug,我给组数据试试?

详细

Test #1:

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

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: 3804kb

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: 0
Accepted
time: 55ms
memory: 3888kb

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
4...

result:

ok 1000 lines

Test #4:

score: 0
Accepted
time: 80ms
memory: 3948kb

input:

10000
9
484630042 51929469
-40468396 -517784096
98214104 -103353239
629244333 -475172587
106398764 153884485
49211709 -44865749
1 10
166321833 -247717657
406208245 668933360
13
548702216 -631976459
37150086 -292461024
707804811 -486185860
239775286 -903166050
10096571 -541890068
686103484 558731937
...

output:

950319193795831919
1661025342421008544
1285164852091455548
1159924751776806668
1206071151805176722
794021230296144371
699991678992587791
1133990718508584290
1486311831172661605
984875884297072200
1327767982175057345
758247019006396699
1355381234262206155
1139262078529131471
1613462877860621700
12392...

result:

ok 10000 lines

Test #5:

score: 0
Accepted
time: 128ms
memory: 5396kb

input:

100
439
471536154 -312612104
155692036 -937312180
-461624056 -357636609
236656684 -911414873
-288656914 -74788431
-465779694 -381475149
-334197401 -903065737
491513067 -447615916
337664889 -852236281
-281689379 -53519178
-159101704 -920779200
-326159514 -95396204
21868593 -994282736
488425383 -41046...

output:

1973162724053130487
2054612790507830954
1726805687754843724
1699420177872986528
2129388571309147631
2198295137903288810
1697185883164440272
1219697450095721478
2027023581922285255
1674691247127206655
1673105966817209954
2179188692918747442
2146544318743443141
2230356305133660648
1676850321902993764
...

result:

ok 100 lines

Test #6:

score: 0
Accepted
time: 101ms
memory: 5168kb

input:

100
1362
-467257672 -466669
-467054869 -478108
-466973270 -481776
-466556983 -499770
-466329414 -508693
-466248017 -511805
-466158865 -513786
-466101273 -515035
-465927700 -518748
-465717624 -522106
-465303448 -528127
-465124548 -530726
-464649746 -536693
-464554872 -537799
-464478196 -538680
-46416...

output:

1666097696993497
1791366071767866
1806187278469532
1683419854733713
1685891971828916
1730190225081651
1787048201197565
1850308098208660
1710694884375502
1826363113637639
1816375352374659
2047431269497691
1549806516003854
1829438662895747
1678707854135065
1687423392883819
2121960009997761
16687219538...

result:

ok 100 lines

Test #7:

score: 0
Accepted
time: 64ms
memory: 13532kb

input:

2
62666
-486101704 -505730259
-486101698 -506082699
-486101689 -506111362
-486101682 -506126031
-486101528 -506293759
-486101259 -506556385
-486101196 -506613483
-486101154 -506648604
-486100935 -506831392
-486100631 -507083675
-486100470 -507199151
-486100233 -507368923
-486100193 -507397039
-48609...

output:

2178736946152219010
1825181940245096152

result:

ok 2 lines

Test #8:

score: 0
Accepted
time: 153ms
memory: 22012kb

input:

2
100000
301945097 76373292
467957663 -286424714
8245445 -597212507
-474204621 -708828667
184159460 105942538
443435905 -429212625
490658771 -382198656
82512047 -612522436
-228221388 -965890088
394789011 -145801151
-106120174 -528202395
428939626 -194437311
497429477 -527407728
365739746 -114818962
...

output:

2502889432701099511
2267250485735988121

result:

ok 2 lines

Test #9:

score: 0
Accepted
time: 152ms
memory: 20076kb

input:

2
100000
221128057 -975244780
-618765360 -785575858
422567455 -906331476
-988680318 -150037424
-929870145 367887908
-757813541 -652471177
291995621 -956419655
-785381507 619012026
468864522 -883270094
-588416522 808557973
859345881 511394814
988105866 153775152
216931298 -976186873
467050734 8842305...

output:

6283183114882825575
6283183188903854361

result:

ok 2 lines

Test #10:

score: 0
Accepted
time: 0ms
memory: 3744kb

input:

7
5
-1000000000 -1000000000
1000000000 -1000000000
1000000000 1000000000
1 0
-1 0
5
1000000000 1000000000
-1000000000 -1000000000
-2 0
-1 0
1 -1
6
1000000000 1000000000
-1000000000 -1000000000
-3 0
-1 0
0 -1
1 -1
4
-1000000000 -1000000000
1000000000 -1000000000
1000000000 1000000000
-1000000000 1000...

output:

4000000000000000000
7000000000
9000000001
-1
6000000002000000000
7999999998000000000
-1

result:

ok 7 lines

Extra Test:

score: 0
Extra Test Passed