QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#693322#9520. Concave HullOldMemoryAC ✓73ms20612kbC++1420.3kb2024-10-31 15:58:162024-10-31 15:58:21

Judging History

This is the latest submission verdict.

  • [2024-10-31 15:58:21]
  • Judged
  • Verdict: AC
  • Time: 73ms
  • Memory: 20612kb
  • [2024-10-31 15:58:16]
  • Submitted

answer

#include<bits/stdc++.h>
using namespace std;
#define int long long
typedef pair<int, int> PII;
typedef long long LL;
const int INF = 0x3f3f3f3f3f3f3f3f;
#define double long double

bool multi = 1;

/*----------计算几何模板----------*/
const double eps = 1e-8,pi = acos(-1.0),inf = 1e30;
int sgn(double x){                     //判断x的大小
    if(fabs(x) < eps) return 0;       //x==0,返回0
    else return x<0?-1:1;              //x<0返回-1,x>0返回1
}
int dcmp(double x, double y){          //比较两个浮点数 
    if(fabs(x - y) < eps) return 0;  //x==y,返回0
    else return x<y ?-1:1;             //x<y返回-1,x>y返回1
}
struct Point{
    double x, y;
    Point(){}
    Point(double x,double y):x(x),y(y){}
    Point operator+(Point B){return Point(x+B.x,y+B.y);}
    Point operator-(Point B){return Point(x-B.x,y-B.y);}
    Point operator*(double k){return Point(x*k,y*k);}
    Point operator/(double k){return Point(x/k,y/k);}
    bool operator==(Point B){return sgn(x-B.x)==0&&sgn(y-B.y)==0;}
    bool operator < (Point B){                  //用于sort()排序,先按x排序,再按y排序
        return sgn(x-B.x)<0 || (sgn(x-B.x)==0 && sgn(y-B.y)<0);
    }
};
typedef Point Vector;
double Dot(Vector A,Vector B){return A.x*B.x+A.y*B.y;}//向量点积
double Cross(Vector A,Vector B){return A.x*B.y-A.y*B.x;}//向量叉积
double Distance(Point A, Point B){ return sqrt((A.x-B.x)*(A.x-B.x)+(A.y-B.y)*(A.y-B.y));}//两点间距离
double Distance2(Point A, Point B){ return (A.x-B.x)*(A.x-B.x)+(A.y-B.y)*(A.y-B.y);}//两点间距离
double Len(Vector A){return sqrt(Dot(A,A));}//向量长度
double Len2(Vector A){return Dot(A,A);}//向量长度的平方
double Angle(Vector A,Vector B){return acos(Dot(A,B)/Len(A)/Len(B));}//向量A与B的夹角
double Area2(Point A,Point B,Point C){return Cross(B-A,C-A);}//以A,B,C三点构成的平行四边形的面积
Vector Rotate(Vector A, double rad){//将向量A逆时针旋转角度rad
    return Vector(A.x*cos(rad)-A.y*sin(rad), A.x*sin(rad)+A.y*cos(rad));
}
Vector Normal(Vector A){return Vector(-A.y/Len(A), A.x/Len(A));}//求向量A的单位法向量(逆时针)
bool Parallel(Vector A, Vector B){return sgn(Cross(A,B)) == 0;}//判断两个向量是否平行或重合

struct Line{
    Point p1,p2;                  //(1)线上的两个点
    Line(){}
    Line(Point p1,Point p2):p1(p1),p2(p2){}
    Line(Point p,double angle){    //(4)根据一个点和倾斜角 angle 确定直线,0<=angle<pi
        p1 = p;
        if(sgn(angle - pi/2) == 0){p2 = (p1 + Point(0,1));}
        else{p2 = (p1 + Point(1,tan(angle)));}
    }
    Line(double a,double b,double c){     //(2)ax+by+c=0
        if(sgn(a) == 0){
            p1 = Point(0,-c/b);
            p2 = Point(1,-c/b);
        }
        else if(sgn(b) == 0){
            p1 = Point(-c/a,0);
            p2 = Point(-c/a,1);
        }
        else{
            p1 = Point(0,-c/b);
            p2 = Point(1,(-c-a)/b);
        }
    }
};
typedef Line Segment;
//点和直线的位置关系
int Point_line_relation(Point p, Line 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上
}
//点和线段:0 点不在线段v上;1 点在线段v上
bool Point_on_seg(Point p, Line v){ 
    return sgn(Cross(p-v.p1, v.p2-v.p1)) == 0 && sgn(Dot(p-v.p1,p-v.p2)) <= 0;
}
//求点到直线的距离
double Dis_point_line(Point p,Line v){
    return fabs(Cross(p-v.p1,v.p2-v.p1))/Distance(v.p1,v.p2);
}
//点在直线上的投影
Point Point_line_proj(Point p, Line v){
    double k = Dot(v.p2-v.p1,p-v.p1)/Len2(v.p2-v.p1);
    return v.p1+(v.p2-v.p1)*k;
}
//点关于直线的对称点
Point Point_line_symmetry(Point p, Line v){
    Point q = Point_line_proj(p,v);
    return Point(2*q.x-p.x,2*q.y-p.y);
}
//点到线段的距离
double Dis_point_seg(Point p, Segment v){
    if(sgn(Dot(p- v.p1,v.p2-v.p1))<0 || sgn(Dot(p- v.p2,v.p1-v.p2))<0)
        return min(Distance(p,v.p1),Distance(p,v.p2));
    return Dis_point_line(p,v);           //点的投影在线段上
}
//两条直线的位置关系
int Line_relation(Line v1, Line 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 相交
}
//两条直线的交点
Point Cross_point(Point a,Point b,Point c,Point d){  //Line1:ab,  Line2:cd
    double s1 = Cross(b-a,c-a);
    double s2 = Cross(b-a,d-a);                    //叉积有正负
    return Point(c.x*s2-d.x*s1,c.y*s2-d.y*s1)/(s2-s1);
}
//两个线段是否相交
bool Cross_segment(Point a,Point b,Point c,Point 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不相交
}
//点和多边形的关系
int Point_in_polygon(Point pt,Point *p,int n){  //点pt,多边形Point *p
    for(int i = 0;i < n;i++){                   //3:点在多边形的顶点上
        if(p[i] == pt)  return 3;
    }
    for(int i = 0;i < n;i++){                   //2:点在多边形的边上
        Line v=Line(p[i],p[(i+1)%n]);
        if(Point_on_seg(pt,v)) return 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:点在外部
}
//多边形的面积
double Polygon_area(Point *p, int n){    //Point *p表示多边形
    double area = 0;
    for(int i = 0;i < n;i++)
        area += Cross(p[i],p[(i+1)%n]);
    return area/2;                    //面积有正负,返回时不能简单地取绝对值
}
Point Polygon_center(Point *p, int n){        //求多边形重心
    Point ans(0,0);
    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;
}

int chidx[200005];

//Convex_hull()求凸包。凸包顶点放在ch中,返回值是凸包的顶点数
int Convex_hull(Point *p,int n,Point *ch){
    n = unique(p,p+n)-p;    //去除重复点    
    sort(p,p+n);            //对点排序:按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) //把后面ch[v-1]改成ch[v-2]也行
        {
            v--;
        }
        chidx[v] = i;
        ch[v++]=p[i];
    }
    int j=v;
    //求上凸包
    for(int i=n-2;i>=0;i--){
        while(v>j && sgn(Cross(ch[v-1]-ch[v-2],p[i]-ch[v-1]))<=0) //把后面ch[v-1]改成ch[v-2]也行
            v--;

        chidx[v] = i;
        ch[v++]=p[i];
    }
    if(n>1) v--;
    return v;                      //返回值v是凸包的顶点数
}
//返回p[left]~p[right]的平面最近点对距离
double Get_Closest_Pair(Point p[],int left,int right){
    sort(p+left,p+right+1,[](Point A,Point B){
        return sgn(A.x-B.x)<0 || (sgn(A.x-B.x)==0 && sgn(A.y-B.y)<0);
    });
    vector<Point> tmp_p(right-left+10);
    function<double(int,int)> Closest_Pair=[&](int left,int right){
        double dis = inf;
        if(left == right) return dis;            //只剩1个点
        if(left + 1 == right) return Distance(p[left], p[right]);//只剩2个点
        int mid = (left+right)/2;                //分治
        double d1 = Closest_Pair(left,mid);      //求s1内的最近点对
        double d2 = Closest_Pair(mid+1,right);   //求s2内的最近点对
        dis = min(d1,d2);
        int k = 0;
        for(int i=left;i<=right;i++)             //在s1和s2中间附近找可能的最小点对
            if(fabs(p[mid].x - p[i].x) <= dis)   //按x坐标来找
                tmp_p[k++] = p[i];
        sort(&tmp_p[0],&tmp_p[k],[](Point A,Point B){return sgn(A.y-B.y)<0;});         //按y坐标排序,用于剪枝。这里不能按x坐标排序
        for(int i=0;i<k;i++)
            for(int j=i+1;j<k;j++){
                if(tmp_p[j].y - tmp_p[i].y >= dis)  break;    //剪枝
                dis = min(dis,Distance(tmp_p[i],tmp_p[j]));
            }
        return dis;  //返回最小距离
    };
    return Closest_Pair(left,right);
}

double Rotating_Calipers2(Point p[], int left, int right) {
    int n = right - left + 1;
    if(n <= 2) {
        return Distance2(p[left], p[right]);
    }
    double res = 0;
    for(int i = 0, j = 2; i < n; i++) {
        while(Area2(p[left + i], p[left + (i + 1) % n], p[left + j]) < Area2(p[left + i], p[left + (i + 1) % n], p[left + (j + 1) % n])) {
            j = (j + 1) % n;
        }
        res = max({res, Distance2(p[left + i], p[left + j]), Distance2(p[left + (i + 1) % n], p[left + j])});
    }
    return res;
}

struct HLine{
	Point p;      //直线上一个点
	Vector v;     //方向向量,它的左边是半平面
	double ang;   //极角,从x正半轴旋转到v的角度
	HLine(){};
	HLine(Point p, Vector v):p(p),v(v){ang = atan2(v.y, v.x);}
	bool operator < (HLine &L){return ang < L.ang;}     //用于排序
};
//点p在线L左边,即点p在线L在外面:
bool OnLeft(HLine L,Point p){return sgn(Cross(L.v,p-L.p))>0;} 
Point Cross_point(HLine a,HLine b){    //两直线交点
    Vector u=a.p-b.p;
	double t=Cross(b.v,u)/Cross(a.v,b.v);
	return a.p+a.v*t;
}
vector<Point> HPI(vector<HLine> L){     //求半平面交,返回凸多边形
	int n=L.size();
	sort(L.begin(),L.end());           //将所有半平面按照极角排序。
	int first,last;                    //指向双端队列的第一个和最后一个元素
	vector<Point> p(n);                //两个相邻半平面的交点
	vector<HLine> q(n);                 //双端队列
	vector<Point> ans;                 //半平面交形成的凸包
	q[first=last=0]=L[0];
	for(int i=1;i<n;i++){
		//情况1:删除尾部的半平面
		while(first<last && !OnLeft(L[i], p[last-1])) last--; 
		//情况2:删除首部的半平面:
		while(first<last && !OnLeft(L[i], p[first]))  first++; 
		q[++last]=L[i];     //将当前的半平面加入双端队列尾部
		//极角相同的两个半平面,保留左边:
		if(fabs(Cross(q[last].v,q[last-1].v)) < eps){ 
		last--;
			if(OnLeft(q[last],L[i].p)) q[last]=L[i];
		}
		//计算队列尾部半平面交点:
		if(first<last) p[last-1]=Cross_point(q[last-1],q[last]);
	}
	//情况3:删除队列尾部的无用半平面
	while(first<last && !OnLeft(q[first],p[last-1])) last--;
	if(last-first<=1) return ans;   //空集
	p[last]=Cross_point(q[last],q[first]);  //计算队列首尾部的交点。
	for(int i=first;i<=last;i++)  ans.push_back(p[i]);   //复制。
	return ans;               //返回凸多边形
}
struct Circle{
    Point c;      //圆心
    double r;     //半径
    Circle(){}
    Circle(Point c,double r):c(c),r(r){}
    Circle(double x,double y,double _r){c=Point(x,y);r = _r;}
};
//点与圆的关系
int Point_circle_relation(Point p, Circle C){
    double dst = Distance(p,C.c);
    if(sgn(dst - C.r) < 0) return 0;       //0 点在圆内
    if(sgn(dst - C.r) ==0) return 1;       //1 圆上
    return 2;                               //2 圆外
}
//直线与圆的关系
int Line_circle_relation(Line v,Circle C){
    double dst = Dis_point_line(C.c,v);
    if(sgn(dst-C.r) < 0) return 0;     //0 直线和圆相交
    if(sgn(dst-C.r) ==0) return 1;     //1 直线和圆相切
    return 2;                               //2 直线在圆外
}
//线段与圆的关系
int Seg_circle_relation(Segment v,Circle C){
    double dst = Dis_point_seg(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是交点。返回值是交点个数
int Line_cross_circle(Line v,Circle C,Point &pa,Point &pb){
    if(Line_circle_relation(v, C)==2)  return 0;//无交点
	Point q = Point_line_proj(C.c,v);          //圆心在直线上的投影点
   	double d = Dis_point_line(C.c,v);          //圆心到直线的距离
	double k = sqrt(C.r*C.r-d*d);    
    if(sgn(k) == 0){                            //1个交点,直线和圆相切
        pa = q;	pb = q;	return 1;
    }
    Point n=(v.p2-v.p1)/ Len(v.p2-v.p1);       //单位向量
    pa = q + n*k;  pb = q - n*k;
    return 2;                                  //2个交点
}
//三点确定圆心
Point circle_center(const Point a, const Point b, const Point c){
    Point center;
    double a1=b.x-a.x, b1=b.y-a.y, c1=(a1*a1+b1*b1)/2;
    double a2=c.x-a.x, b2=c.y-a.y, c2=(a2*a2+b2*b2)/2;
    double d =a1*b2-a2*b1;
    center.x =a.x+(c1*b2-c2*b1)/d;
    center.y =a.y+(a1*c2-a2*c1)/d;
    return center;
}
//求最小圆覆盖
void min_cover_circle(Point *p, int n, Circle &C){
    random_shuffle(p, p + n);             //随机函数,打乱所有点。这一步很重要
    Point c=p[0]; 
    double r=0;                          //从第1个点p0开始。圆心为p0,半径为0
    for(int i=1;i<n;i++)                  //扩展所有点
        if(sgn(Distance(p[i],c)-r)>0){    //点pi在圆外部
            c=p[i]; r=0;                  //重新设置圆心为pi,半径为0
            for(int j=0;j<i;j++)          //重新检查前面所有的点。
                if(sgn(Distance(p[j],c)-r)>0){   //两点定圆
                    c.x=(p[i].x + p[j].x)/2;
                    c.y=(p[i].y + p[j].y)/2;
                    r=Distance(p[j],c);
                    for(int k=0;k<j;k++)
                        if (sgn(Distance(p[k],c)-r)>0){   //两点不能定圆,就三点定圆
                            c=circle_center(p[i],p[j],p[k]);
                            r=Distance(p[i], c);
                        }
                }
        }
    C={c,r};
}

struct Point3{             //三维点
    double x,y,z;
    Point3(){}
    Point3(double x,double y,double z):x(x),y(y),z(z){}
    Point3 operator + (Point3 B){return Point3(x+B.x,y+B.y,z+B.z);}
    Point3 operator - (Point3 B){return Point3(x-B.x,y-B.y,z-B.z);}
    Point3 operator * (double k){return Point3(x*k,y*k,z*k);}
    Point3 operator / (double k){return Point3(x/k,y/k,z/k);}
    bool operator == (Point3 B){	return sgn(x-B.x)==0 && sgn(y-B.y)==0 && sgn(z-B.z)==0;}
};
typedef Point3 Vector3;    //三维向量
double Distance(Vector3 A,Vector3 B){
	return sqrt((A.x-B.x)*(A.x-B.x)+(A.y-B.y)*(A.y-B.y)+ (A.z-B.z)*(A.z-B.z));    
}
struct Line3{
    Point3 p1,p2;
    Line3(){}
    Line3(Point3 p1,Point3 p2):p1(p1),p2(p2){}
};
typedef Line3 Segment3;       //定义线段,两端点是Point p1,p2
//三维点积
double Dot(Vector3 A,Vector3 B){return A.x*B.x+A.y*B.y+A.z*B.z;}
//求向量A的长度
double Len(Vector3 A){ return sqrt(Dot(A, A));}
//求向量A的长度的平方
double Len2(Vector3 A){ return Dot(A, A);}
//求向量A与B的夹角
double Angle(Vector3 A,Vector3 B){return acos(Dot(A,B)/Len(A)/Len(B));}
//三维叉积
Vector3 Cross(Vector3 A,Vector3 B){
	return Point3(A.y*B.z-A.z*B.y, A.z*B.x-A.x*B.z, A.x*B.y-A.y*B.x);
}
//求三个点构成的三角形面积的2倍
double Area2(Point3 A,Point3 B,Point3 C){return Len(Cross(B-A, C-A));}
//三维:点在直线上
bool Point_line_relation(Point3 p,Line3 v){
    return sgn( Len(Cross(v.p1-p,v.p2-p))) == 0 && sgn(Dot(v.p1-p,v.p2-p))== 0;
}
double Dis_point_line(Point3 p, Line3 v)           //三维:点到直线距离
{  return Len(Cross(v.p2-v.p1,p-v.p1))/Distance(v.p1,v.p2); }
//三维:点到线段距离。
double Dis_point_seg(Point3 p, Segment3 v){
    if(sgn(Dot(p- v.p1,v.p2-v.p1)) < 0 || sgn(Dot(p- v.p2,v.p1-v.p2)) < 0)
        return min(Distance(p,v.p1),Distance(p,v.p2));
    return Dis_point_line(p,v);
}
//三维:点 p 在直线上的投影
Point3 Point_line_proj(Point3 p, Line3 v){
    double k=Dot(v.p2-v.p1,p-v.p1)/Len2(v.p2-v.p1);
    return v.p1+(v.p2-v.p1)*k;
}
struct Plane{
    Point3 p1,p2,p3;     //平面上的三个点
    Plane(){}
    Plane(Point3 p1,Point3 p2,Point3 p3):p1(p1),p2(p2),p3(p3){}
};
//平面的法向量
Point3 Pvec(Point3 A, Point3 B, Point3 C){return Cross(B-A,C-A);}
Point3 Pvec(Plane f){return Cross(f.p2-f.p1,f.p3-f.p1);}
//四点共平面
bool Point_on_plane(Point3 A,Point3 B,Point3 C,Point3 D){
    return sgn(Dot(Pvec(A,B,C),D-A)) == 0;
}
//两平面平行
int Parallel(Plane f1, Plane f2){ return Len(Cross(Pvec(f1),Pvec(f2))) < eps; }
//两平面垂直
int Vertical(Plane f1, Plane f2){ return sgn(Dot(Pvec(f1),Pvec(f2)))==0; }
//直线与平面的交点
int Line_cross_plane(Line3 u,Plane f,Point3 &p){
    Point3 v = Pvec(f);                           //平面的法向量
    double x = Dot(v, u.p2-f.p1);
    double y = Dot(v, u.p1-f.p1);
    double d = x-y;
    if(sgn(x) == 0 && sgn(y) == 0) return -1;    //-1:v在f上
    if(sgn(d) == 0) return 0;                    //0:v与f平行
    p = ((u.p1 * x)-(u.p2 * y))/d;               //v与f相交
    return 1;
}
//四面体有向体积*6
double volume4(Point3 a,Point3 b,Point3 c,Point3 d){
return Dot(Cross(b-a,c-a),d-a); }
//最小球覆盖
double min_cover_ball(Point3 *p, int n){
    double T=100.0;                    //初始温度
    double delta = 0.98;               //降温系数
    Point3 c = p[0];                   //球心
    int pos;
    double r;                          //半径
    while(T>eps)    {                  //eps是终止温度
        pos = 0; r = 0;                //初始:p[0]是球心,半径是0
        for(int i=0; i<n; i++)         //迭代:找距离球心最远的点
            if(Distance(c,p[i])>r){
                r = Distance(c,p[i]);  //距离球心最远的点肯定在球周上
                pos = i;
            }
        c.x += (p[pos].x-c.x)/r*T;     //逼近最后的解
        c.y += (p[pos].y-c.y)/r*T;
        c.z += (p[pos].z-c.z)/r*T;
        T *= delta;                    //降温
    }
    return r;
}
/*----------计算几何模板----------*/

const int N = 2e5 + 10;
int totn;
Point p[N];
int outchn;
Point outch[N];
int inpn;
Point inp[N];
int inchn;
Point inch[N];

void solve() {
    inpn = 0;
    cin >> totn;
    for(int i = 0; i < totn; i++) {
        int x, y;
        cin >> x >> y;
        p[i] = Point(x, y);
    }
    if(totn <= 3) {
        cout << -1 << '\n';
        return;
    }
    outchn = Convex_hull(p, totn, outch);
    double Soutch = Polygon_area(outch, outchn) * 2;
    double ans = 0;
    vector<bool> st(totn);
    for(int i = 0; i < outchn; i++) {
        st[chidx[i]] = true;
    }
    for(int i = 0; i < totn; i++) {
        if(!st[i]) {
            inp[inpn++] = p[i];
        }
    }
    if(inpn == 0) {
        cout << -1 << '\n';
        return;
    }
    if(inpn <= 3) {
        for(int i = 0; i < inpn; i++) {
            for(int j = 0; j < outchn; j++) {
                double Stri = Area2(outch[j], outch[(j + 1) % outchn], inp[i]);
                ans = max(ans, Soutch - Stri);
            }
        }
    }else{
        inchn = Convex_hull(inp, inpn, inch);
        int j = 0;
        double tmn = inf;
        for(int i = 0; i < inchn; i++) {
            double tS = Area2(inch[i], outch[0], outch[1]);
            if(tmn > tS) {
                tmn = tS;
                j = i;
            }
        }
        double mnS = inf;
        // cerr << mnS << '\n';
        for(int i = 0; i < outchn; i++) {
            while(Area2(outch[i], outch[(i + 1) % outchn], inch[(j + 1) % inchn]) + 1e-10 < Area2(outch[i], outch[(i + 1) % outchn], inch[j])) {
                j = (j + 1) % inchn;
            }
            mnS = min(mnS, Area2(outch[i], outch[(i + 1) % outchn], inch[j]));
        }
        ans = max(ans, Soutch - mnS);
    }

    cout << (int)round(ans) << '\n';

}

signed main() {
    ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
    int T = 1;
    if(multi) cin >> T;
    while(T--) {
        solve();
    }

    return 0;
}

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

詳細信息

Test #1:

score: 100
Accepted
time: 1ms
memory: 9940kb

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: 0ms
memory: 11856kb

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: 24ms
memory: 12000kb

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: 34ms
memory: 11724kb

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: 64ms
memory: 11988kb

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: 52ms
memory: 11904kb

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: 33ms
memory: 18560kb

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: 73ms
memory: 20612kb

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: 69ms
memory: 14556kb

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

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