QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#194195#7521. Find the Gapucup-team1447#AC ✓238ms1756kbC++2315.3kb2023-09-30 19:31:472023-09-30 19:31:48

Judging History

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

  • [2023-09-30 19:31:48]
  • 评测
  • 测评结果:AC
  • 用时:238ms
  • 内存:1756kb
  • [2023-09-30 19:31:47]
  • 提交

answer

#include <stdio.h>
#include <random>
#include <queue>
std::mt19937_64 rng(0x3d03d);
#include <math.h>
#include <time.h>
#include <assert.h>
#include <string.h>
#include <algorithm>
#include <vector>
#include <bitset>
#include <set>
#define int long long
#define ld(x) printf("%lld\n",x)
// #define int unsigned
using std::vector;
using vi=vector<int>;
using pi=std::pair<int,int>;
using vpi=vector<pi>;
#define x first
#define y second
const int mod=998244353;
inline int min(int a,int b){return a>b?b:a;}
inline int max(int a,int b){return a<b?b:a;}
inline int read()
{
    int num=0,f=1;char c=getchar();
    while(c<48||c>57){if(c=='-')f=-1;c=getchar();}
    while(c>47&&c<58)num=num*10+(c^48),c=getchar();
    return num*f;
}

typedef int arr[1000005];
#define db double
#define double long double
struct point{db x,y,z;}a[55];
namespace banzi{

using namespace std;

#define MAX_N 110

/*------------------常量区-------------------*/

const double INF        = 1e10;      // 无穷大
const double EPS        = 1e-12;      // 计算精度
const double PI         = acos(-1.0);// PI
const int PINXING       = 0;         // 平行
const int XIANGJIAO     = 1;         // 相交
const int XIANGLI       = 3;         // 相离
const int GONGXIAN      = 2;         // 共线
const int CHONGDIE      = -1;        // 重叠
const int INSIDE        = 1;         // 点在图形内部
const int OUTSIDE       = 0;         // 点在图形外部
const int BORDER        = 2;         // 点在图形边界

/*-----------------类型定义区----------------*/

struct Point {              // 二维点或矢量
    double x, y;
    //double angle, dis;
    Point() {}
    Point(double x0, double y0): x(x0), y(y0) {}
    void read()
    {
        scanf("%Lf%Lf",&x,&y);
    }
};

struct Line {               // 二维的直线或线段
    Point p1, p2;
    Line() {}
    Line(Point p10, Point p20): p1(p10), p2(p20) {}
    void read()
    {
        scanf("%Lf%Lf%Lf%Lf",&p1.x,&p1.y,&p2.x,&p2.y);
    }
};

struct Rect {              // 用长宽表示矩形的方法 w, h分别表示宽度和高度
    double w, h;
    Rect() {}
    Rect(double _w,double _h) : w(_w),h(_h) {}
};
struct Rect_2 {             // 表示矩形,左下角坐标是(xl, yl),右上角坐标是(xh, yh)
    double xl, yl, xh, yh;
    Rect_2() {}
    Rect_2(double _xl,double _yl,double _xh,double _yh) : xl(_xl),yl(_yl),xh(_xh),yh(_yh) {}
};
struct Circle {            //圆
    Point c;
    double r;
    Circle() {}
    Circle(Point _c,double _r) :c(_c),r(_r) {}
};

typedef vector<Point> Polygon;      // 二维多边形
typedef vector<Point> Points;       // 二维点集

/*-------------------基本函数区---------------------*/

inline double max(double x,double y)
{
    return x > y ? x : y;
}
inline double min(double x, double y)
{
    return x > y ? y : x;
}
inline bool ZERO(double x)              // x == 0
{
    return (fabs(x) < EPS);
}
inline bool ZERO(Point p)               // p == 0
{
    return (ZERO(p.x) && ZERO(p.y));
}

inline bool EQ(double x, double y)      // eqaul, x == y
{
    return (fabs(x - y) < EPS);
}
inline bool NEQ(double x, double y)     // not equal, x != y
{
    return (fabs(x - y) >= EPS);
}
inline bool LT(double x, double y)     // less than, x < y
{
    return ( NEQ(x, y) && (x < y) );
}
inline bool GT(double x, double y)     // greater than, x > y
{
    return ( NEQ(x, y) && (x > y) );
}
inline bool LEQ(double x, double y)     // less equal, x <= y
{
    return ( EQ(x, y) || (x < y) );
}
inline bool GEQ(double x, double y)     // greater equal, x >= y
{
    return ( EQ(x, y) || (x > y) );
}

// 输出浮点数前,防止输出-0.00调用该函数进行修正!
inline double FIX(double x)
{
    return (fabs(x) < EPS) ? 0 : x;
}



/*~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~*/
//-------------------3D 区域----------------------------//

struct Point3D {            //三维点或矢量
    double x, y, z;
    Point3D() {}
    Point3D(double x0, double y0, double z0): x(x0), y(y0), z(z0) {}
    void read()
    {
        scanf("%Lf%Lf%Lf",&x,&y,&z);
    }
};

struct Line3D {             // 三维的直线或线段
    Point3D p1, p2;
    Line3D() {}
    Line3D(Point3D p10, Point3D p20): p1(p10), p2(p20) {}
    void read()
    {
        scanf("%Lf%Lf%Lf%Lf%Lf%Lf",&p1.x,&p1.y,&p1.z,&p2.x,&p2.y,&p2.z);
    }
};

struct Area3D{
    Point3D p1,p2,p3;
    Area3D(){}
    Area3D(Point3D p10, Point3D p20,Point3D p30): p1(p10), p2(p20), p3(p30){}
    void read()
    {
        p1.read(); p2.read(); p3.read();
        //scanf("%Lf%Lf%Lf%Lf%Lf%Lf%Lf%Lf%Lf",&p1.x,&p1.y,&p1.z,&p2.x,&p2.y,&p2.z,&p3.x,&p3.y,&p3.z);
    }
};

inline bool ZERO(Point3D p)              // p == 0
{
    return (ZERO(p.x) && ZERO(p.y) && ZERO(p.z));
}

//////////////////////////////////////////////////////////////////////////////////////
//三维矢量运算
bool operator==(Point3D p1, Point3D p2)
{
    return ( EQ(p1.x, p2.x) && EQ(p1.y, p2.y) && EQ(p1.z, p2.z) );
}
bool operator<(Point3D p1, Point3D p2)
{
    if (NEQ(p1.x, p2.x)) {
        return (p1.x < p2.x);
    } else if (NEQ(p1.y, p2.y)) {
        return (p1.y < p2.y);
    } else {
        return (p1.z < p2.z);
    }
}
Point3D operator+(Point3D p1, Point3D p2)
{
    return Point3D(p1.x + p2.x, p1.y + p2.y, p1.z + p2.z);
}
Point3D operator-(Point3D p1, Point3D p2)
{
    return Point3D(p1.x - p2.x, p1.y - p2.y, p1.z - p2.z);
}
Point3D operator * (const Point3D& A, double p) { return Point3D(A.x*p, A.y*p, A.z*p); }
Point3D operator / (const Point3D& A, double p) { return Point3D(A.x/p, A.y/p, A.z/p); }

Point3D operator*(Point3D p1, Point3D p2) // 计算叉乘 p1 x p2
{
    return Point3D(p1.y * p2.z - p1.z * p2.y,
                   p1.z * p2.x - p1.x * p2.z,
                   p1.x * p2.y - p1.y * p2.x );
}
double operator&(Point3D p1, Point3D p2) { // 计算点积 p1·p2
    return (p1.x * p2.x + p1.y * p2.y + p1.z * p2.z);
}
double Norm(Point3D p) // 计算矢量p的模
{
    return sqrt(p.x * p.x + p.y * p.y + p.z * p.z);
}

//取平面法向量
Point3D GetV(Area3D s){
    return (s.p1-s.p2)*(s.p2-s.p3);
}

//判三点共线
int PointOnLine(Point3D p1,Point3D p2,Point3D p3){
    return ZERO( (p1-p2)*(p2-p3) );
}


//判四点共面
int PointOnArea(Point3D a,Point3D b,Point3D c,Point3D d){
    return ZERO( GetV(Area3D(a, b, c))&(d-a) );
}

//求三维空间中两点间的距离
double Dis(Point3D p1, Point3D p2)
{
    return sqrt((p1.x-p2.x)*(p1.x-p2.x)+(p1.y-p2.y)*(p1.y-p2.y)+(p1.z-p2.z)*(p1.z-p2.z));
}
// 求三维空间中点到直线的距离
double Dis(Point3D p, Line3D L)
{
    if(L.p1==L.p2) return Dis(p, L.p1);
    return Norm((p - L.p1) * (L.p2 - L.p1)) / Norm(L.p2 - L.p1);
}

bool OnLine(Point3D p, Line3D L) // 判断三维空间中点p是否在直线L上
{
    if(L.p1==L.p2 && p==L.p1) return true;//共点时,返回true
    return ZERO( (p - L.p1) * (L.p2 - L.p1) );
}
bool OnLineSeg(Point3D p, Line3D L) // 判断三维空间中点p是否在线段l上
{
    return ( ZERO((L.p1 - p) * (L.p2 - p)) &&
            EQ( Norm(p - L.p1) + Norm(p - L.p2), Norm(L.p2 - L.p1)) );
}

// 点p到平面Ap-Al的距离。
double Dis(Point3D p, Point3D Ap, Point3D Al) {
    return fabs((p-Ap)&Al)/Norm(Al); // 如果不取绝对值,得到的是有向距离
}

// 点p在平面Ap-Al上的投影。
Point3D PointToArea(Point3D p,Point3D Ap, Point3D Al) {
    Al=Al/(Norm(Al));//把Al变成法向量。
    return p-Al*((p-Ap)&Al);
}
//得到点p到直线L的距离,并返回p到直直线L的最近点rep
double PointToLine(Point3D p,Line3D L,Point3D& rep)
{
    if(L.p1==L.p2)
    {
        rep=L.p1;
        return Dis(p,L.p1);
    }
    Point3D a,b;
    a = L.p2-L.p1;
    b = p-L.p1;
    double dis12 = Dis(L.p1,L.p2);
    double dis = ( Norm(a*b) )/dis12;
    
    double k = (a&b)/(Norm(a)*dis12) ;
    rep = L.p1+(L.p2-L.p1)*k;
    return dis;
}
//求两条直线之间的关系(三维)
//输入:两条不为点的直线
//输出:相交返回XIANGJIAO和交点p,平行返回PINGXING,共线返回GONGXIAN
int LineAndLine(Line3D L1,Line3D L2,Point3D &p)
{
    Point3D px,py;
    px = L1.p1 - L1.p2;
    py = L2.p1 - L2.p2;
    
    if( ZERO(px*py) )//平行或者共线
    {
        if( ZERO( (L2.p1-L1.p1)*py ) ) //共线
        {
            return GONGXIAN;
        }
        return PINXING;
    }
    //判断是否共面
    Point3D tp=(L1.p1-L2.p1)*py;
    if( !ZERO(tp&px) ) return XIANGLI;//XIANGLI与平行相同
    
    p = L1.p1;
    Point3D tp1=(L2.p1-L1.p1)*(L2.p1-L2.p2);
    Point3D tp2=(L1.p2-L1.p1)*(L2.p1-L2.p2);
    double _t = Norm(tp1)/Norm(tp2);
    //tp1和tp2肯定是共线的,如果反向则_t 为负
    if( LT( (tp1&tp2),0 ) ) _t*=-1;
    p.x += (L1.p2.x-L1.p1.x)*_t;
    p.y += (L1.p2.y-L1.p1.y)*_t;
    p.z += (L1.p2.z-L1.p1.z)*_t;
    return XIANGJIAO;
}

//空间两直线最近点对。直线不能平行,直线不能为点.
//ans1为直线a1,b1上的最近点
Point3D ans1,ans2;
double SegSegDistance(Point3D a1, Point3D b1, Point3D a2, Point3D b2)
{
    Point3D v1 = (a1-b1), v2 = (a2-b2);
    Point3D N = v1*v2;
    Point3D ab = (a1-a2);
    double ans = (N&ab) / Norm(N);
    Point3D p1 = a1, p2 = a2;
    Point3D d1 = b1-a1, d2 = b2-a2;
    double t1, t2;
    t1 = ((p2-p1)*d2 )&(d1*d2);
    t2 = ((p2-p1)*d1 )&(d1*d2);
    double dd = Norm( (d1*d2) );
    t1 /= dd*dd;
    t2 /= dd*dd;
    ans1=a1+(b1-a1)*t1;
    ans2=a2+(b2-a2)*t2;
    return fabs(ans);
}

//直线与平面交
int LineAndArea(Line3D l1,Point3D Ap,Point3D Al,Point3D &p)
{
    //输入直线,和平面的点法式
    //第一步,判断直线与平面是否平行。
    if( ZERO((l1.p2-l1.p1)&Al)  ) return 0;//直线与平面平行。
    double _t =( (Ap-l1.p1)&Al ) / ((l1.p1-l1.p2)&Al);
    p = l1.p1+(l1.p1-l1.p2)*_t;
    return 1;
}

void dfs(int x,double &len)
{
    len++;
    dfs(x-1,len);
    dfs(x-2,len);
}

//空间两直线最近点对
//注意:直线不能平行
double LineAndLine(Line3D l1,Line3D l2,Point3D &p1,Point3D &p2)
{
    //先求出法向量
    Point3D v1,v2;
    v1 = l1.p2-l1.p1;
    v2 = l2.p2-l2.p1;
    Point3D vt=v1*v2;
    //然后先把l2投影到 l1所在的平面上
    double len = ((l2.p1-l1.p1)&vt)/Norm(vt);
    double normvt = -len/Norm(vt);
    
    vt.x = vt.x*normvt;
    vt.y = vt.y*normvt;
    vt.z = vt.z*normvt;
    
    Line3D tl2;
    tl2.p1 = l2.p1+vt;
    tl2.p2 = l2.p2+vt;
    
    int sign=LineAndLine(l1, tl2, p1);
    /*
     //测试用
     if(sign!=XIANGJIAO)
     {
     int x=0;
     printf("%Lf\n",len/x);
     dfs(100000000,len);
     }
     */
    return fabs(len);
}

//已知空间四面体6条边,求体积
double P( double a,double b,double c,double d,double e ){ return a*(b*c-d*e); }
double Get4V(int OA,int OB,int OC,int AB,int CA,int BC)
{
    OA*=OA;OB*=OB;OC*=OC;AB*=AB;CA*=CA;BC*=BC;
    double ans=0;
    ans+=P( OA,OB,OC,(OB+OC-BC)/2.0,(OB+OC-BC)/2.0 );
    ans-=P( (OA+OB-AB)/2.0,(OA+OB-AB)/2.0,OC,(OA+OC-CA)/2.0,(OB+OC-BC)/2.0 );
    ans+=P( (OA+OC-CA)/2.0,(OA+OB-AB)/2.0,(OB+OC-BC)/2.0,OB,(OA+OC-CA)/2.0);
    return sqrt(ans/36);
}

//求两面相交,平行或共面返回PINGXING,否则返回XIANGJIAO和直线rel
int AreaAndArea(Area3D a1,Area3D a2,Line3D &rel)
{
    Point3D va1 = GetV(a1),va2 = GetV(a2);
    Point3D lv = va1*va2;//相交直线的方向向量
    if( ZERO(lv) )//平行
    {
        return PINXING;
    }
    //然后得到某一个交点
    Point3D p1;
    if(LineAndArea(Line3D(a1.p1,a1.p2), a2.p1, va2, p1) == 0)
       if(LineAndArea(Line3D(a1.p1,a1.p3), a2.p1, va2, p1) == 0)
           LineAndArea(Line3D(a1.p2,a1.p3), a2.p1, va2, p1);
    rel.p1 = p1; rel.p2 = p1 + (lv*10);
    return XIANGJIAO;
}

//已知3点坐标,求平面ax+by+cz+d=0;
void GetAreaABCD(Point3D p1,Point3D p2,Point3D p3,double &a,double &b,double &c,double &d)
{
    a = ( (p2.y-p1.y)*(p3.z-p1.z)-(p2.z-p1.z)*(p3.y-p1.y) );
    b = ( (p2.z-p1.z)*(p3.x-p1.x)-(p2.x-p1.x)*(p3.z-p1.z) );
    c = ( (p2.x-p1.x)*(p3.y-p1.y)-(p2.y-p1.y)*(p3.x-p1.x) );
    d = ( 0-(a*p1.x+b*p1.y+c*p1.z) );
}

//////////////////////////////////////////////////////////////////////////////////////


/*---------------------代码区---------------------------*/
}
signed main()
{
	int n=read();
	for(int i=1;i<=n;i++)a[i].x=read(),a[i].y=read(),a[i].z=read();
	int gx=1;

	for(int i=3;i<=n;i++)
	{
		if((a[i].x-a[1].x)*(a[i-1].y-a[1].y)!=(a[i].y-a[1].y)*(a[i-1].x-a[1].x))gx=0;
		if((a[i].x-a[1].x)*(a[i-1].z-a[1].z)!=(a[i].z-a[1].z)*(a[i-1].x-a[1].x))gx=0;
		if((a[i].z-a[1].z)*(a[i-1].y-a[1].y)!=(a[i].y-a[1].y)*(a[i-1].z-a[1].z))gx=0;
	}
	if(gx)return puts("0"),0;
	double ans=1e18;
	for(int i=1;i<=n;i++)
		for(int j=1;j<i;j++)
		{
			db A=a[i].x-a[j].x;
			db B=a[i].y-a[j].y;
			db C=a[i].z-a[j].z;
			db xs=sqrt(A*A+B*B+C*C);
			db mn=1e18,mx=-1e18;
			for(int k=1;k<=n;k++)
				mn=std::min(mn,A*a[k].x+B*a[k].y+C*a[k].z),
				mx=std::max(mx,A*a[k].x+B*a[k].y+C*a[k].z);
			ans=std::min(ans,(mx-mn)/xs);
		}
	for(int i=1;i<=n;i++)
		for(int j=1;j<i;j++)
			for(int k=1;k<=n;k++)if(k!=i&&k!=j)
			{
				banzi::Point3D A1(a[i].x,a[i].y,a[i].z);
				banzi::Point3D B1(a[j].x,a[j].y,a[j].z);
				banzi::Point3D C1(a[k].x,a[k].y,a[k].z);
				banzi::Line3D l(A1,B1);
				banzi::Point3D Q;
				double zz=banzi::PointToLine(C1,l,Q);
				// printf("%d %d %d:%.3lf\n",i,j,k,zz);
				auto [A,B,C]=Q;
				A-=a[k].x;
				B-=a[k].y;
				C-=a[k].z;
				
				db xs=sqrt(A*A+B*B+C*C);
				db mn=1e18,mx=-1e18;
				for(int k=1;k<=n;k++)
					mn=std::min(mn,A*a[k].x+B*a[k].y+C*a[k].z),
					mx=std::max(mx,A*a[k].x+B*a[k].y+C*a[k].z);
			// if((mx-mn)/xs<1)printf("%d %d %d\n",i,j,k);
				ans=std::min(ans,(mx-mn)/xs);
			}
	for(int i=1;i<=n;i++)
		for(int j=1;j<i;j++)
			for(int k=1;k<j;k++)
			{
				banzi::Point3D A1(a[i].x,a[i].y,a[i].z);
				banzi::Point3D B1(a[j].x,a[j].y,a[j].z);
				banzi::Point3D C1(a[k].x,a[k].y,a[k].z);
				banzi::Line3D l(A1,B1);
				banzi::Point3D Q;
				double zz=banzi::PointToLine(C1,l,Q);
				if(zz<1e-10)continue;
				banzi::Area3D T(A1,B1,C1);
				auto [A,B,C]=banzi::GetV(T);
				// printf("%d %d %d:%.3lf\n",i,j,k,zz);
				db xs=sqrt(A*A+B*B+C*C);
				db mn=1e18,mx=-1e18;
				for(int k=1;k<=n;k++)
					mn=std::min(mn,A*a[k].x+B*a[k].y+C*a[k].z),
					mx=std::max(mx,A*a[k].x+B*a[k].y+C*a[k].z);
				ans=std::min(ans,(mx-mn)/xs);
			}
	for(int i=1;i<=n;i++)
		for(int j=1;j<i;j++)
			for(int k=1;k<i;k++)
			for(int l=1;l<k;l++)if(l!=j)
			{
				banzi::Point3D A1(a[i].x,a[i].y,a[i].z);
				banzi::Point3D B1(a[j].x,a[j].y,a[j].z);
				banzi::Point3D C1(a[k].x,a[k].y,a[k].z);
				banzi::Point3D D1(a[l].x,a[l].y,a[l].z);
				banzi::Point3D E1=A1+(C1-D1),F;
				banzi::Line3D X(A1,B1),Y(A1,E1);
				if(banzi::LineAndLine(X,Y,F)==banzi::GONGXIAN)continue;
				banzi::Area3D T(A1,B1,E1);
				auto [A,B,C]=banzi::GetV(T);
				db xs=sqrt(A*A+B*B+C*C);
				db mn=1e18,mx=-1e18;
				for(int k=1;k<=n;k++)
					mn=std::min(mn,A*a[k].x+B*a[k].y+C*a[k].z),
					mx=std::max(mx,A*a[k].x+B*a[k].y+C*a[k].z);
				ans=std::min(ans,(mx-mn)/xs);
			}
	printf("%.16Lf\n",ans);
	fprintf(stderr,"%.12lf\n",1.*clock()/CLOCKS_PER_SEC);
	return 0;
}

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

詳細信息

Test #1:

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

input:

8
1 1 1
1 1 2
1 2 1
1 2 2
2 1 1
2 1 2
2 2 1
2 2 2

output:

1.0000000000000000

result:

ok found '1.000000000', expected '1.000000000', error '0.000000000'

Test #2:

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

input:

5
1 1 1
1 2 1
1 1 2
1 2 2
2 1 1

output:

0.7071067811865475

result:

ok found '0.707106781', expected '0.707106781', error '0.000000000'

Test #3:

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

input:

50
973 1799 4431
1036 1888 4509
1099 1977 4587
1162 2066 4665
1225 2155 4743
1288 2244 4821
1351 2333 4899
1414 2422 4977
1540 2600 5133
1603 2689 5211
1666 2778 5289
1729 2867 5367
1792 2956 5445
1855 3045 5523
1918 3134 5601
1981 3223 5679
2044 3312 5757
2107 3401 5835
2170 3490 5913
2296 3668 606...

output:

0

result:

ok found '0.000000000', expected '0.000000000', error '-0.000000000'

Test #4:

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

input:

50
4532 3245 1339
4624 3260 1345
4716 3275 1351
4808 3290 1357
4900 3305 1363
5084 3335 1375
5176 3350 1381
5268 3365 1387
5360 3380 1393
5452 3395 1399
5544 3410 1405
5728 3440 1417
5820 3455 1423
5912 3470 1429
6096 3500 1441
6188 3515 1447
6280 3530 1453
6372 3545 1459
6464 3560 1465
6556 3575 14...

output:

0

result:

ok found '0.000000000', expected '0.000000000', error '-0.000000000'

Test #5:

score: 0
Accepted
time: 235ms
memory: 1680kb

input:

50
1 70 7443
1 138 5063
2 109 5971
3 23 8874
3 152 4359
4 59 7507
5 50 7715
5 73 6910
7 25 8376
7 103 5646
8 3 9039
9 83 6132
9 142 4067
10 124 4590
11 140 3923
12 168 2836
13 46 6999
13 84 5669
13 189 1994
13 229 594
15 171 2410
16 94 4998
20 38 6530
20 125 3485
21 78 5023
22 210 296
23 117 3444
25...

output:

0.0000000000000000

result:

ok found '0.000000000', expected '0.000000000', error '-0.000000000'

Test #6:

score: 0
Accepted
time: 235ms
memory: 1636kb

input:

50
1 95 5991
3 22 9019
25 103 5199
25 141 3603
38 103 4952
39 139 3421
59 6 8627
60 48 6844
66 33 7360
107 88 4271
109 188 33
112 177 438
114 107 3340
122 77 4448
123 169 565
127 1 7545
142 161 540
143 70 4343
146 153 800
156 129 1618
162 63 4276
162 150 622
166 93 2940
173 78 3437
180 143 574
189 1...

output:

0.0000000000000000

result:

ok found '0.000000000', expected '0.000000000', error '-0.000000000'

Test #7:

score: 0
Accepted
time: 235ms
memory: 1608kb

input:

50
14 3658 1218
17 32 7984
741 1906 5773
755 8668 1019
834 2386 4591
1306 3866 7044
2304 2895 120
2450 8613 7374
2595 1919 2119
2610 9866 9419
2694 2845 2941
2838 2702 7608
2883 4143 4049
3082 4800 3611
3338 6703 9039
3424 2035 1863
3471 2672 5858
4339 1330 2029
4720 6970 4719
4853 387 5866
5415 975...

output:

9341.5658961839690511

result:

ok found '9341.565896184', expected '9341.565896184', error '0.000000000'

Test #8:

score: 0
Accepted
time: 235ms
memory: 1704kb

input:

50
159 8547 6997
489 5655 1694
934 6033 5986
1088 9448 2840
1395 7938 709
2007 7008 9167
2429 7436 2364
2670 7425 7568
2694 7703 9701
2797 9081 2872
2813 1423 1081
3105 5669 4792
3277 4229 8596
3332 8329 1497
3476 1696 448
3738 996 508
4050 3854 1609
4105 9677 5306
4383 5848 5996
4583 3186 9948
4723...

output:

8144.1657216481557162

result:

ok found '8144.165721648', expected '8144.165721648', error '0.000000000'

Test #9:

score: 0
Accepted
time: 235ms
memory: 1600kb

input:

50
140 3759 310
325 657 967
337 2969 2340
341 1234 8436
953 3787 949
1137 9272 5791
1597 8518 7711
2642 3171 9590
2808 2188 9307
2932 7143 773
3075 4055 3861
3479 2654 2788
3516 1372 2617
4202 2476 6906
4446 5279 7147
4586 2815 3229
4956 839 7424
5038 5342 8758
5418 8882 6013
5533 4047 3030
5746 498...

output:

9146.8970275720116208

result:

ok found '9146.897027572', expected '9146.897027572', error '0.000000000'

Test #10:

score: 0
Accepted
time: 236ms
memory: 1688kb

input:

50
27 8992 3447
97 1870 5176
255 7759 6929
287 8477 8753
424 6928 3781
561 5383 3443
800 5654 5210
812 829 5236
1058 6953 2716
1129 2576 4054
1525 5088 1278
1743 7422 862
2004 2404 6472
2721 5900 258
3024 9464 4959
3027 8887 4260
3344 6066 5823
3715 5789 9796
3814 5999 277
3915 9604 12
4072 663 3333...

output:

9143.9151071077945048

result:

ok found '9143.915107108', expected '9143.915107108', error '0.000000000'

Test #11:

score: 0
Accepted
time: 235ms
memory: 1680kb

input:

50
514 6841 888
673 9023 8705
686 4780 9173
742 2761 5439
894 585 5417
894 1436 3585
1433 6876 9685
1728 8358 463
1736 4442 7163
1758 4362 4567
2175 4091 8630
2631 4226 6098
2648 9912 4504
2752 7427 8318
2806 3482 839
3158 6527 3601
3682 4472 5007
3764 3518 942
4096 1948 2138
4116 9501 5003
4122 318...

output:

9169.7362972988372967

result:

ok found '9169.736297299', expected '9169.736297299', error '0.000000000'

Test #12:

score: 0
Accepted
time: 235ms
memory: 1684kb

input:

50
169 7924 553
239 9844 8248
244 7970 4414
476 6722 3954
732 477 1641
966 6652 3944
981 2690 6362
1230 3488 921
1372 3614 4691
1395 5858 4433
1452 253 94
1754 6818 6578
1768 4318 6261
1814 7730 593
2189 7047 1844
2539 4933 4531
2882 8069 831
3188 3902 6915
3217 5522 9148
3552 8575 5975
3909 9654 63...

output:

9150.1352330805712159

result:

ok found '9150.135233081', expected '9150.135233081', error '0.000000000'

Test #13:

score: 0
Accepted
time: 235ms
memory: 1680kb

input:

50
96 1653 9109
238 3924 6708
484 8684 2909
750 5493 3159
817 1112 3722
909 918 7323
923 3270 4679
963 4055 5335
1059 9040 4043
1083 5006 2224
1225 2043 1082
1257 6421 570
1884 3398 6379
2010 4066 3604
2270 4127 1357
2714 1776 7355
2916 2914 3705
2960 5403 5768
3613 4179 9807
3792 79 6885
3879 5691 ...

output:

8959.8159048599395895

result:

ok found '8959.815904860', expected '8959.815904860', error '0.000000000'

Test #14:

score: 0
Accepted
time: 235ms
memory: 1748kb

input:

50
466 4419 3421
491 2907 9714
506 1869 8685
525 7133 5224
896 6803 414
1018 5218 7102
1291 9905 269
1375 3915 9212
1541 6176 2118
1730 3165 4221
2295 589 9786
2311 9068 6251
2651 8939 9186
2867 6164 7925
3140 5988 5013
3296 7112 5300
3381 16 2989
3495 511 7235
3603 8547 7675
3623 8113 8461
3877 810...

output:

9149.7699374277137201

result:

ok found '9149.769937428', expected '9149.769937428', error '0.000000000'

Test #15:

score: 0
Accepted
time: 235ms
memory: 1648kb

input:

50
78 4 4902
193 9001 5084
419 4402 642
578 8090 167
584 9616 4407
1533 4560 8566
1686 179 6908
1951 2381 3902
2010 6519 3351
2083 2122 2314
2394 7870 934
2618 9113 1012
2796 3688 4096
2928 7277 9546
3051 3575 6416
3096 3711 3736
3200 6179 1933
3288 8818 9981
3534 8346 2715
3740 8112 1351
3772 6404 ...

output:

8392.8052222522244588

result:

ok found '8392.805222252', expected '8392.805222252', error '0.000000000'

Test #16:

score: 0
Accepted
time: 238ms
memory: 1688kb

input:

50
705 6359 9590
709 9583 837
1100 7827 378
1118 5958 5626
1190 2811 3485
1270 1818 6313
1567 9075 1709
1655 2572 4135
1766 951 2003
1870 352 7790
2509 20 2260
2733 1466 7061
2744 3417 6230
2820 4147 5340
3058 9727 4331
3429 7782 3337
3463 9788 5114
4180 5867 2244
4426 3621 3218
4762 3055 4802
4880 ...

output:

8573.3526712546009607

result:

ok found '8573.352671255', expected '8573.352671255', error '0.000000000'

Test #17:

score: 0
Accepted
time: 235ms
memory: 1744kb

input:

50
165 8302 5584
700 7675 6720
881 7965 4577
889 1338 8010
1116 1639 795
1186 8218 2543
1217 7776 3846
1430 9843 1018
1454 998 4454
1624 4047 4040
1624 4230 8183
1682 2296 8486
2100 7651 4049
2147 7426 4916
2524 519 5402
2743 51 6480
3284 5924 8050
3330 5196 9459
3517 4263 5230
3624 6365 595
4043 16...

output:

9058.7419077400535814

result:

ok found '9058.741907740', expected '9058.741907740', error '0.000000000'

Test #18:

score: 0
Accepted
time: 235ms
memory: 1696kb

input:

50
100 1845 5981
212 8119 8531
272 2837 9427
393 3708 6901
483 121 2429
545 9916 3687
636 9192 6039
1470 8344 6819
1643 6549 7092
1675 2261 8181
1847 7777 6817
2015 8137 940
2305 9959 58
2336 8793 1450
2399 6420 8272
3224 4903 4156
3225 8648 6448
3274 9687 8319
3431 9580 3305
3488 1299 9485
3622 588...

output:

8012.8679177212904312

result:

ok found '8012.867917721', expected '8012.867917721', error '0.000000000'

Test #19:

score: 0
Accepted
time: 235ms
memory: 1652kb

input:

50
19 2681 1646
27 1110 5179
338 6651 3754
507 2567 7601
557 2595 480
580 2720 3352
584 937 6894
591 6885 5697
607 2834 2727
667 9502 9812
789 6818 9256
1122 253 5727
1436 7824 2840
1725 3949 3495
1733 297 2443
1901 7810 3668
1962 2763 775
2279 4850 913
2461 2951 2842
2491 8181 7544
2605 6682 3557
2...

output:

9064.9273876616389227

result:

ok found '9064.927387662', expected '9064.927387662', error '0.000000000'

Test #20:

score: 0
Accepted
time: 235ms
memory: 1724kb

input:

50
194 7049 1546
264 8020 6837
847 8285 1854
862 5862 4012
904 9367 6797
1575 4158 8361
1835 2084 4014
1850 418 2351
2003 2813 7003
2043 6346 1467
2046 1800 8962
2530 7010 6913
2992 2316 6887
3399 1789 8276
3518 7325 8772
3545 55 1523
3686 1275 9961
4019 1016 5463
4486 7468 3485
4580 1802 8881
4782 ...

output:

8101.7417890617074101

result:

ok found '8101.741789062', expected '8101.741789062', error '0.000000000'

Test #21:

score: 0
Accepted
time: 235ms
memory: 1608kb

input:

50
103 6485 4333
511 6113 4211
639 8425 3693
739 7999 8239
808 5095 8775
826 1656 7709
1173 7565 7160
1320 1179 6855
1326 2043 1063
1604 267 6466
1625 6615 6094
1697 6022 77
1851 6269 1588
2138 4521 288
2648 9706 898
2990 2590 1837
3016 4963 4557
3037 3834 5432
3161 6627 3844
3448 9741 2733
3753 137...

output:

9128.5981542508040620

result:

ok found '9128.598154251', expected '9128.598154251', error '0.000000000'

Test #22:

score: 0
Accepted
time: 231ms
memory: 1732kb

input:

50
261 4050 3501
264 4793 7406
737 6575 4542
1143 98 723
1453 9810 529
1676 7893 2790
1936 4005 5944
1954 7716 9379
1980 9534 2502
1981 5073 3147
2117 2971 8441
2144 7774 7451
2279 6190 3900
2292 3909 6381
2723 5981 433
2784 7435 9645
2939 1908 8904
3063 3468 7719
3552 6932 890
3563 3953 5582
3899 2...

output:

9066.8759579019781647

result:

ok found '9066.875957902', expected '9066.875957902', error '0.000000000'

Test #23:

score: 0
Accepted
time: 235ms
memory: 1656kb

input:

50
124 8775 2089
502 2885 6276
699 9285 7955
880 6499 8738
1293 8478 4996
1294 7009 3514
1314 6660 8895
1583 49 517
2090 7900 446
2711 1216 9700
2792 1533 727
2840 1552 2842
2965 7790 8788
3491 4707 3568
3704 4977 960
3941 1201 6460
4003 4114 5115
4012 2234 9330
4073 6968 5235
4310 6469 6799
4630 59...

output:

8820.2507463745485428

result:

ok found '8820.250746375', expected '8820.250746375', error '0.000000000'

Test #24:

score: 0
Accepted
time: 235ms
memory: 1688kb

input:

50
317 4576 3269
526 4973 5972
1295 1304 4839
1508 3932 1994
1959 7684 48
2001 8395 8132
2232 7475 8511
2667 7154 1453
2747 5229 1254
3229 3535 1083
3346 2197 3601
3430 3753 3090
3432 5831 4752
3526 2117 2434
3868 3250 5864
3909 6614 6027
4133 4435 3421
4352 4192 3560
4559 1398 36
4671 3830 7598
476...

output:

8710.1031577498627660

result:

ok found '8710.103157750', expected '8710.103157750', error '0.000000000'

Test #25:

score: 0
Accepted
time: 220ms
memory: 1644kb

input:

50
237 1777 4827
439 298 4986
845 3946 3189
891 4118 3219
914 4204 3234
960 4376 3264
1015 722 1293
1029 4634 3309
1069 5704 7228
1080 1878 9626
1121 4978 3369
1144 5064 3384
1213 5322 3429
1236 5408 3444
1259 5494 3459
1305 5666 3489
1328 5752 3504
1397 6010 3549
1420 6096 3564
1535 6526 3639
1581 ...

output:

8321.8866496089023439

result:

ok found '8321.886649609', expected '8321.886649609', error '0.000000000'

Test #26:

score: 0
Accepted
time: 184ms
memory: 1656kb

input:

50
1491 6638 6932
2019 8838 4932
2359 1341 7441
3979 7642 8342
4764 4812 3543
4800 4814 613
4813 4890 638
4865 5194 738
4891 5346 788
4904 5422 813
4943 5650 888
4956 5726 913
4982 5878 963
4995 5954 988
5008 6030 1013
5034 6182 1063
5047 6258 1088
5060 6334 1113
5073 6410 1138
5086 6486 1163
5099 6...

output:

7406.0718773578760978

result:

ok found '7406.071877358', expected '7406.071877358', error '0.000000000'

Test #27:

score: 0
Accepted
time: 151ms
memory: 1700kb

input:

50
293 8979 6557
651 1626 1890
654 1682 1935
657 1738 1980
663 1850 2070
666 1906 2115
669 1962 2160
675 2074 2250
678 2130 2295
681 2186 2340
687 2298 2430
693 2410 2520
696 2466 2565
720 2914 2925
723 2970 2970
726 3026 3015
735 3194 3150
738 3250 3195
741 3306 3240
753 3530 3420
765 3754 3600
768...

output:

2809.0579417754716236

result:

ok found '2809.057941775', expected '2809.057941775', error '0.000000000'

Test #28:

score: 0
Accepted
time: 125ms
memory: 1732kb

input:

50
2805 3371 1430
2848 3397 1465
2977 3475 1570
3106 3553 1675
3149 3579 1710
3235 3631 1780
3278 3657 1815
3364 3709 1885
3450 3761 1955
3493 3787 1990
3579 3839 2060
3708 3917 2165
3794 3969 2235
4095 4151 2480
4181 4203 2550
4353 4307 2690
4439 4359 2760
4568 4437 2865
4697 4515 2970
4783 4567 30...

output:

710.1290841062068713

result:

ok found '710.129084106', expected '710.129084106', error '0.000000000'

Test #29:

score: 0
Accepted
time: 115ms
memory: 1696kb

input:

50
3712 669 4937
3844 779 5025
3976 889 5113
4108 999 5201
4174 1054 5245
4240 1109 5289
4306 1164 5333
4372 1219 5377
4438 1274 5421
4570 1384 5509
4636 1439 5553
4648 4162 7960
4702 1494 5597
4768 1549 5641
4834 1604 5685
4900 1659 5729
4966 1714 5773
5098 1824 5861
5230 1934 5949
5296 1989 5993
5...

output:

0.0000000000000000

result:

ok found '0.000000000', expected '0.000000000', error '-0.000000000'

Test #30:

score: 0
Accepted
time: 236ms
memory: 1716kb

input:

50
2 4 9006
3 23 5330
3 46 1029
4 17 6329
4 50 158
5 12 7141
5 22 5271
10 36 2038
13 43 360
16 33 1861
18 15 4981
18 18 4420
19 10 5793
20 3 6979
20 8 6044
21 35 872
23 22 3057
26 26 1940
26 36 70
27 19 3126
29 27 1384
37 23 1148
41 10 3087
49 8 2477
51 18 361
56 4 2364
57 7 1680
64 1 1941
64 8 632
...

output:

8277.7009779167169414

result:

ok found '8277.700977917', expected '8277.700977917', error '0.000000000'

Test #31:

score: 0
Accepted
time: 235ms
memory: 1696kb

input:

50
2 156 5164
2 162 4990
2 241 2699
4 321 67
7 205 2963
8 35 7737
8 284 516
9 75 6421
9 248 1404
10 200 2640
10 219 2089
11 27 7501
11 198 2542
12 95 5373
13 186 2578
15 132 3832
16 106 4430
16 161 2835
18 58 5510
20 157 2327
22 113 3291
24 65 4371
26 11 5625
26 96 3160
27 52 4280
27 151 1409
28 28 ...

output:

6600.9519863733361542

result:

ok found '6600.951986373', expected '6600.951986373', error '0.000000000'

Test #32:

score: 0
Accepted
time: 235ms
memory: 1608kb

input:

50
1 51 8290
2 17 9300
2 295 404
4 211 2936
5 259 1322
6 262 1148
7 37 8270
7 125 5454
9 137 4914
10 199 2852
12 205 2504
12 222 1960
20 92 5496
21 244 554
22 161 3132
23 77 5742
32 149 2736
33 82 4802
36 120 3352
37 110 3594
37 161 1962
38 113 3420
44 51 4936
47 16 5822
50 65 4020
52 35 4824
52 60 ...

output:

3583.1247421375544966

result:

ok found '3583.124742138', expected '3583.124742138', error '0.000000000'

Test #33:

score: 0
Accepted
time: 235ms
memory: 1628kb

input:

50
2 34 3220
10 19 6149
23 16 6655
27 5 8816
78 1 9255
94 7 7949
102 5 8291
106 5 8263
125 29 3354
176 35 1803
201 21 4414
203 23 4002
216 40 528
254 24 3446
270 35 1145
277 1 7862
283 15 5034
288 5 6989
331 24 2907
353 28 1957
367 32 1063
378 16 4170
416 26 1914
419 1 6868
439 33 360
440 4 6124
444...

output:

3469.2100180184424294

result:

ok found '3469.210018018', expected '3469.210018018', error '0.000000000'

Test #34:

score: 0
Accepted
time: 235ms
memory: 1684kb

input:

50
8 297 8499
16 1111 4413
28 1196 3964
75 942 5140
190 63 9305
252 308 7956
307 269 8041
346 503 6793
420 119 8565
446 87 8673
515 692 5510
654 1259 2397
723 1003 3539
786 188 7488
822 1402 1346
843 1569 469
844 1352 1552
972 421 5951
1015 1216 1890
1106 681 4383
1121 1117 2173
1134 463 5417
1166 1...

output:

3265.9835690111973796

result:

ok found '3265.983569011', expected '3265.983569011', error '0.000000000'

Test #35:

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

input:

1
3 5 7

output:

0

result:

ok found '0.000000000', expected '0.000000000', error '-0.000000000'

Test #36:

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

input:

2
2 3 3
7 5 10000

output:

0

result:

ok found '0.000000000', expected '0.000000000', error '-0.000000000'

Test #37:

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

input:

3
1 2 3
2 3 4
3 4 5

output:

0

result:

ok found '0.000000000', expected '0.000000000', error '-0.000000000'

Test #38:

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

input:

3
1 2 3
7 8 9
100 200 10000

output:

0.0000000000000000

result:

ok found '0.000000000', expected '0.000000000', error '-0.000000000'