QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#284777 | #7934. Christmas Sky | ucup-team896# | AC ✓ | 79ms | 92800kb | C++23 | 18.4kb | 2023-12-16 14:59:47 | 2023-12-16 14:59:48 |
Judging History
answer
/*
* @Author: cmk666
* @Created time: 2023-12-16 14:54:39
* @Last Modified time: 2023-12-16 14:59:35
*/
#pragma GCC optimize("Ofast", "unroll-loops")
#include<bits/stdc++.h>
#ifdef LOCAL
#include"debug.h"
#else
#define D(...) ((void)0)
#endif
using namespace std; using ll = long long;
#define For(i, j, k) for ( int i = (j) ; i <= (k) ; i++ )
#define Fol(i, j, k) for ( int i = (j) ; i >= (k) ; i-- )
namespace FastIO
{
// ------------------------------
#define IN_HAS_NEG
// #define OUT_HAS_NEG
// #define CHK_EOF
// #define DISABLE_MMAP
// ------------------------------
#if __cplusplus < 201400
#error Please use C++14 or higher.
#endif
#if __cplusplus > 201700
#define INLINE_V inline
#else
#define INLINE_V
#endif
#if ( defined(LOCAL) || defined(_WIN32) ) && !defined(DISABLE_MMAP)
#define DISABLE_MMAP
#endif
#ifndef DISABLE_MMAP
#include<sys/mman.h>
#endif
#ifdef LOCAL
inline char gc() { return getchar(); }
inline void pc(char c) { putchar(c); }
#else
#ifdef DISABLE_MMAP
INLINE_V constexpr int _READ_SIZE = 1 << 18;
INLINE_V static char _read_buffer[_READ_SIZE], *_read_ptr = nullptr, *_read_ptr_end = nullptr;
inline char gc()
{
if ( __builtin_expect(_read_ptr == _read_ptr_end, false) )
{
_read_ptr = _read_buffer;
_read_ptr_end = _read_buffer + fread(_read_buffer, 1, _READ_SIZE, stdin);
#ifdef CHK_EOF
if ( __builtin_expect(_read_ptr == _read_ptr_end, false) ) return EOF;
#endif
}
return *_read_ptr++;
}
#else
INLINE_V static const char *_read_ptr = (const char *)mmap(nullptr, INT_MAX, 1, 2, 0, 0);
inline char gc() { return *_read_ptr++; }
#endif
INLINE_V constexpr int _WRITE_SIZE = 1 << 18;
INLINE_V static char _write_buffer[_WRITE_SIZE], *_write_ptr = _write_buffer;
inline void pc(char c)
{
*_write_ptr++ = c;
if ( __builtin_expect(_write_buffer + _WRITE_SIZE == _write_ptr, false) )
{
fwrite(_write_buffer, 1, _write_ptr - _write_buffer, stdout);
_write_ptr = _write_buffer;
}
}
INLINE_V struct _auto_flush
{
inline ~_auto_flush() { fwrite(_write_buffer, 1, _write_ptr - _write_buffer, stdout); }
} _auto_flush;
#endif
#ifdef CHK_EOF
inline constexpr bool _isdigit(char c) { return ( c & 16 ) && c != EOF; }
inline constexpr bool _isgraph(char c) { return c > 32 && c != EOF; }
#else
inline constexpr bool _isdigit(char c) { return c & 16; }
inline constexpr bool _isgraph(char c) { return c > 32; }
#endif
template < class T >
INLINE_V constexpr bool _is_integer = numeric_limits < T >::is_integer;
template < class T >
INLINE_V constexpr bool _is_signed = numeric_limits < T >::is_signed;
template < class T >
INLINE_V constexpr bool _is_unsigned = _is_integer < T > && !_is_signed < T >;
template <> INLINE_V constexpr bool _is_integer < __int128 > = true;
template <> INLINE_V constexpr bool _is_integer < __uint128_t > = true;
template <> INLINE_V constexpr bool _is_signed < __int128 > = true;
template <> INLINE_V constexpr bool _is_unsigned < __uint128_t > = true;
#undef INLINE_V
inline void read(char &c) { do c = gc(); while ( !_isgraph(c) ); }
inline void read_cstr(char *s)
{
char c = gc(); while ( !_isgraph(c) ) c = gc();
while ( _isgraph(c) ) *s++ = c, c = gc();
*s = 0;
}
inline void read(string &s)
{
char c = gc(); s.clear(); while ( !_isgraph(c) ) c = gc();
while ( _isgraph(c) ) s.push_back(c), c = gc();
}
#ifdef IN_HAS_NEG
template < class T, enable_if_t < _is_signed < T >, int > = 0 >
inline void read(T &x)
{
char c = gc(); bool f = true; x = 0;
while ( !_isdigit(c) ) { if ( c == 45 ) f = false; c = gc(); }
if ( f ) while ( _isdigit(c) ) x = x * 10 + ( c & 15 ), c = gc();
else while ( _isdigit(c) ) x = x * 10 - ( c & 15 ), c = gc();
}
template < class T, enable_if_t < _is_unsigned < T >, int > = 0 >
#else
template < class T, enable_if_t < _is_integer < T >, int > = 0 >
#endif
inline void read(T &x)
{
char c = gc(); while ( !_isdigit(c) ) c = gc();
x = 0; while ( _isdigit(c) ) x = x * 10 + ( c & 15 ), c = gc();
}
inline void write(char c) { pc(c); }
inline void write_cstr(const char *s) { while ( *s ) pc(*s++); }
inline void write(const string &s) { for ( char c : s ) pc(c); }
#ifdef OUT_HAS_NEG
template < class T, enable_if_t < _is_signed < T >, int > = 0 >
inline void write(T x)
{
char buffer[numeric_limits < T >::digits10 + 1]; int digits = 0;
if ( x >= 0 ) do buffer[digits++] = ( x % 10 ) | 48, x /= 10; while ( x );
else { pc(45); do buffer[digits++] = -( x % 10 ) | 48, x /= 10; while ( x ); }
while ( digits ) pc(buffer[--digits]);
}
template < class T, enable_if_t < _is_unsigned < T >, int > = 0 >
#else
template < class T, enable_if_t < _is_integer < T >, int > = 0 >
#endif
inline void write(T x)
{
char buffer[numeric_limits < T >::digits10 + 1]; int digits = 0;
do buffer[digits++] = ( x % 10 ) | 48, x /= 10; while ( x );
while ( digits ) pc(buffer[--digits]);
}
template < int N > struct _tuple_io_helper
{
template < class ...T >
static inline void _read(tuple < T... > &x)
{ _tuple_io_helper < N - 1 >::_read(x), read(get < N - 1 > (x)); }
template < class ...T >
static inline void _write(const tuple < T... > &x)
{ _tuple_io_helper < N - 1 >::_write(x), pc(32), write(get < N - 1 > (x)); }
};
template <> struct _tuple_io_helper < 1 >
{
template < class ...T >
static inline void _read(tuple < T... > &x) { read(get < 0 > (x)); }
template < class ...T >
static inline void _write(const tuple < T... > &x) { write(get < 0 > (x)); }
};
template < class ...T >
inline void read(tuple < T... > &x) { _tuple_io_helper < sizeof...(T) >::_read(x); }
template < class ...T >
inline void write(const tuple < T... > &x) { _tuple_io_helper < sizeof...(T) >::_write(x); }
template < class T1, class T2 >
inline void read(pair < T1, T2 > &x) { read(x.first), read(x.second); }
template < class T1, class T2 >
inline void write(const pair < T1, T2 > &x) { write(x.first), pc(32), write(x.second); }
template < class T1, class ...T2 >
inline void read(T1 &x, T2 &...y) { read(x), read(y...); }
template < class ...T >
inline void read_cstr(char *x, T *...y) { read_cstr(x), read_cstr(y...); }
template < class T1, class ...T2 >
inline void write(const T1 &x, const T2 &...y) { write(x), write(y...); }
template < class ...T >
inline void write_cstr(const char *x, const T *...y) { write_cstr(x), write_cstr(y...); }
template < class T >
inline void print(const T &x) { write(x); }
inline void print_cstr(const char *x) { write_cstr(x); }
template < class T1, class ...T2 >
inline void print(const T1 &x, const T2 &...y) { print(x), pc(32), print(y...); }
template < class ...T >
inline void print_cstr(const char *x, const T *...y) { print_cstr(x), pc(32), print_cstr(y...); }
inline void println() { pc(10); }
inline void println_cstr() { pc(10); }
template < class ...T >
inline void println(const T &...x) { print(x...), pc(10); }
template < class ...T >
inline void println_cstr(const T *...x) { print_cstr(x...), pc(10); }
}
using namespace FastIO;
namespace GEO // https://www.luogu.com.cn/blog/ChenXingLing/post-xue-xi-bi-ji-ji-suan-ji-he-quan-jia-tong
{
/*一:【准备工作】*/
#define LD long double
#define LL long long
#define Re int
#define Vector Point
using namespace std;
const int N=262144+3;
const LD eps=1e-8,Pi=acos(-1.0);
inline int dcmp(LD a){return a<-eps?-1:(a>eps?1:0);}//处理精度
inline LD Abs(LD a){return a*dcmp(a);}//取绝对值
struct Point{
LD x,y;Point(LD X=0,LD Y=0){x=X,y=Y;}
inline void in(){scanf("%lf%lf",&x,&y);}
inline void out(){printf("%.2lf %.2lf\n",x,y);}
};
/*二:【向量】*/
inline LD Dot(Vector a,Vector b){return a.x*b.x+a.y*b.y;}//【点积】
inline LD Cro(Vector a,Vector b){return a.x*b.y-a.y*b.x;}//【叉积】
inline LD Len(Vector a){return sqrt(Dot(a,a));}//【模长】
inline LD Angle(Vector a,Vector b){return acos(Dot(a,b)/Len(a)/Len(b));}//【两向量夹角】
inline Vector Normal(Vector a){return Vector(-a.y,a.x);}//【法向量】
inline Vector operator+(Vector a,Vector b){return Vector(a.x+b.x,a.y+b.y);}
inline Vector operator-(Vector a,Vector b){return Vector(a.x-b.x,a.y-b.y);}
inline Vector operator*(Vector a,LD b){return Vector(a.x*b,a.y*b);}
inline bool operator==(Point a,Point b){return !dcmp(a.x-b.x)&&!dcmp(a.y-b.y);}//两点坐标重合则相等
/*三:【点、向量的位置变换】*/
/*1.【点、向量的旋转】*/
inline Point turn_P(Point a,LD theta){//【点A\向量A顺时针旋转theta(弧度)】
LD x=a.x*cos(theta)+a.y*sin(theta);
LD y=-a.x*sin(theta)+a.y*cos(theta);
return Point(x,y);
}
inline Point turn_PP(Point a,Point b,LD theta){//【将点A绕点B顺时针旋转theta(弧度)】
LD x=(a.x-b.x)*cos(theta)+(a.y-b.y)*sin(theta)+b.x;
LD y=-(a.x-b.x)*sin(theta)+(a.y-b.y)*cos(theta)+b.y;
return Point(x,y);
}
/*四:【图形与图形之间的关系】*/
/*1.【点与线段】*/
inline int pan_PL(Point p,Point a,Point b){//【判断点P是否在线段AB上】
return !dcmp(Cro(p-a,b-a))&&dcmp(Dot(p-a,p-b))<=0;//做法一
// return !dcmp(Cro(p-a,b-a))&&dcmp(min(a.x,b.x)-p.x)<=0&&dcmp(p.x-max(a.x,b.x))<=0&&dcmp(min(a.y,b.y)-p.y)<=0&&dcmp(p.y-max(a.y,b.y))<=0;//做法二
//PA,AB共线且P在AB之间(其实也可以用len(p-a)+len(p-b)==len(a-b)判断,但是精度损失较大)
}
inline LD dis_PL(Point p,Point a,Point b){//【点P到线段AB距离】
if(a==b)return Len(p-a);//AB重合
Vector x=p-a,y=p-b,z=b-a;
if(dcmp(Dot(x,z))<0)return Len(x);//P距离A更近
if(dcmp(Dot(y,z))>0)return Len(y);//P距离B更近
return Abs(Cro(x,z)/Len(z));//面积除以底边长
}
/*2.【点与直线】*/
inline int pan_PL_(Point p,Point a,Point b){//【判断点P是否在直线AB上】
return !dcmp(Cro(p-a,b-a));//PA,AB共线
}
inline Point FootPoint(Point p,Point a,Point b){//【点P到直线AB的垂足】
Vector x=p-a,y=p-b,z=b-a;
LD len1=Dot(x,z)/Len(z),len2=-1.0*Dot(y,z)/Len(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;//将PF延长一倍即可
}
/*3.【线与线】*/
inline Point cross_LL(Point a,Point b,Point c,Point d){//【两直线AB,CD的交点】
Vector x=b-a,y=d-c,z=a-c;
return a+x*(Cro(y,z)/Cro(x,y));//点A加上向量AF
}
inline int pan_cross_L_L(Point a,Point b,Point c,Point d){//【判断直线AB与线段CD是否相交】
return pan_PL(cross_LL(a,b,c,d),c,d);//直线AB与直线CD的交点在线段CD上
}
inline int pan_cross_LL(Point a,Point b,Point c,Point d){//【判断两线段AB,CD是否相交】
LD c1=Cro(b-a,c-a),c2=Cro(b-a,d-a);
LD d1=Cro(d-c,a-c),d2=Cro(d-c,b-c);
return dcmp(c1)*dcmp(c2)<0&&dcmp(d1)*dcmp(d2)<0;//分别在两侧
}
/*4.【点与多边形】*/
inline int PIP(Point *P,Re n,Point a){//【射线法】判断点A是否在任意多边形Poly以内
Re cnt=0;LD tmp;
for(Re i=1;i<=n;++i){
Re j=i<n?i+1:1;
if(pan_PL(a,P[i],P[j]))return 2;//点在多边形上
if(a.y>=min(P[i].y,P[j].y)&&a.y<max(P[i].y,P[j].y))//纵坐标在该线段两端点之间
tmp=P[i].x+(a.y-P[i].y)/(P[j].y-P[i].y)*(P[j].x-P[i].x),cnt+=dcmp(tmp-a.x)>0;//交点在A右方
}
return cnt&1;//穿过奇数次则在多边形以内
}
inline int judge(Point a,Point L,Point R){//判断AL是否在AR右边
return dcmp(Cro(L-a,R-a))>0;//必须严格以内
}
inline int PIP_(Point *P,Re n,Point a){//【二分法】判断点A是否在凸多边形Poly以内
//点按逆时针给出
if(judge(P[1],a,P[2])||judge(P[1],P[n],a))return 0;//在P[1_2]或P[1_n]外
if(pan_PL(a,P[1],P[2])||pan_PL(a,P[1],P[n]))return 2;//在P[1_2]或P[1_n]上
Re l=2,r=n-1;
while(l<r){//二分找到一个位置pos使得P[1]_A在P[1_pos],P[1_(pos+1)]之间
Re mid=l+r+1>>1;
if(judge(P[1],P[mid],a))l=mid;
else r=mid-1;
}
if(judge(P[l],a,P[l+1]))return 0;//在P[pos_(pos+1)]外
if(pan_PL(a,P[l],P[l+1]))return 2;//在P[pos_(pos+1)]上
return 1;
}
/*5.【线与多边形】*/
/*6.【多边形与多边形】*/
inline int judge_PP(Point *A,Re n,Point *B,Re m){//【判断多边形A与多边形B是否相离】
for(Re i1=1;i1<=n;++i1){
Re j1=i1<n?i1+1:1;
for(Re i2=1;i2<=m;++i2){
Re j2=i2<m?i2+1:1;
if(pan_cross_LL(A[i1],A[j1],B[i2],B[j2]))return 0;//两线段相交
if(PIP(B,m,A[i1])||PIP(A,n,B[i2]))return 0;//点包含在内
}
}
return 1;
}
/*五:【图形面积】*/
/*1.【任意多边形面积】*/
inline LD PolyArea(Point *P,Re n){//【任意多边形P的面积】
LD S=0;
for(Re i=1;i<=n;++i)S+=Cro(P[i],P[i<n?i+1:1]);
return S/2.0;
}
/*2.【圆的面积并】*/
/*3.【三角形面积并】*/
/*六:【凸包】*/
/*1.【求凸包】*/
inline bool cmp1(Vector a,Vector b){return a.x==b.x?a.y<b.y:a.x<b.x;};//按坐标排序
inline int ConvexHull(Point *P,Re n,Point *cp){//【水平序Graham扫描法(Andrew算法)】求凸包
sort(P+1,P+n+1,cmp1);
Re t=0;
for(Re i=1;i<=n;++i){//下凸包
while(t>1&&dcmp(Cro(cp[t]-cp[t-1],P[i]-cp[t-1]))<=0)--t;
cp[++t]=P[i];
}
Re St=t;
for(Re i=n-1;i>=1;--i){//上凸包
while(t>St&&dcmp(Cro(cp[t]-cp[t-1],P[i]-cp[t-1]))<=0)--t;
cp[++t]=P[i];
}
return --t;//要减一
}
/*2.【旋转卡壳】*/
/*3.【半平面交】*/
struct Line{
Point a,b;LD k;Line(Point A=Point(0,0),Point B=Point(0,0)){a=A,b=B,k=atan2(b.y-a.y,b.x-a.x);}
inline bool operator<(const Line &O)const{return dcmp(k-O.k)?dcmp(k-O.k)<0:judge(O.a,O.b,a);}//如果角度相等则取左边的
}L[N],Q[N];
inline Point cross(Line L1,Line L2){return cross_LL(L1.a,L1.b,L2.a,L2.b);}//获取直线L1,L2的交点
inline int judge(Line L,Point a){return dcmp(Cro(a-L.a,L.b-L.a))>0;}//判断点a是否在直线L的右边
inline int halfcut(Line *L,Re n,Point *P){//【半平面交】
sort(L+1,L+n+1);Re m=n;n=0;
for(Re i=1;i<=m;++i)if(i==1||dcmp(L[i].k-L[i-1].k))L[++n]=L[i];
Re h=1,t=0;
for(Re i=1;i<=n;++i){
while(h<t&&judge(L[i],cross(Q[t],Q[t-1])))--t;//当队尾两个直线交点不是在直线L[i]上或者左边时就出队
while(h<t&&judge(L[i],cross(Q[h],Q[h+1])))++h;//当队头两个直线交点不是在直线L[i]上或者左边时就出队
Q[++t]=L[i];
}
while(h<t&&judge(Q[h],cross(Q[t],Q[t-1])))--t;
while(h<t&&judge(Q[t],cross(Q[h],Q[h+1])))++h;
n=0;
for(Re i=h;i<=t;++i)P[++n]=cross(Q[i],Q[i<t?i+1:h]);
return n;
}
/*4.【闵可夫斯基和】*/
Vector V1[N],V2[N];
inline int Mincowski(Point *P1,Re n,Point *P2,Re m,Vector *V){//【闵可夫斯基和】求两个凸包{P1},{P2}的向量集合{V}={P1+P2}构成的凸包
for(Re i=1;i<=n;++i)V1[i]=P1[i<n?i+1:1]-P1[i];
for(Re i=1;i<=m;++i)V2[i]=P2[i<m?i+1:1]-P2[i];
Re t=0,i=1,j=1;V[++t]=P1[1]+P2[1];
while(i<=n&&j<=m)++t,V[t]=V[t-1]+(dcmp(Cro(V1[i],V2[j]))>0?V1[i++]:V2[j++]);
while(i<=n)++t,V[t]=V[t-1]+V1[i++];
while(j<=m)++t,V[t]=V[t-1]+V2[j++];
return t;
}
/*5.【动态凸包】*/
/*七:【圆】*/
/*1.【三点确定一圆】*/
#define S(a) ((a)*(a))
struct Circle{Point O;LD r;Circle(Point P,LD R=0){O=P,r=R;}};
inline Circle getCircle(Point A,Point B,Point C){//【三点确定一圆】暴力解方程
LD x1=A.x,y1=A.y,x2=B.x,y2=B.y,x3=C.x,y3=C.y;
LD D=((S(x2)+S(y2)-S(x3)-S(y3))*(y1-y2)-(S(x1)+S(y1)-S(x2)-S(y2))*(y2-y3))/((x1-x2)*(y2-y3)-(x2-x3)*(y1-y2));
LD E=(S(x1)+S(y1)-S(x2)-S(y2)+D*(x1-x2))/(y2-y1);
LD F=-(S(x1)+S(y1)+D*x1+E*y1);
return Circle(Point(-D/2.0,-E/2.0),sqrt((S(D)+S(E)-4.0*F)/4.0));
}
inline Circle getcircle(Point A,Point B,Point C){//【三点确定一圆】向量垂心法
Point P1=(A+B)*0.5,P2=(A+C)*0.5;
Point O=cross_LL(P1,P1+Normal(B-A),P2,P2+Normal(C-A));
return Circle(O,Len(A-O));
}
/*2.【最小覆盖圆】*/
inline int PIC(Circle C,Point a){return dcmp(Len(a-C.O)-C.r)<=0;}//判断点A是否在圆C内
// inline void Random(Point *P,Re n){for(Re i=1;i<=n;++i)swap(P[i],P[rand()%n+1]);}//随机一个排列
inline Circle Min_Circle(Point *P,Re n){//【求点集P的最小覆盖圆】
// random_shuffle(P+1,P+n+1);
// Random(P,n);
shuffle(P+1,P+n+1,mt19937(time(nullptr)));
Circle C=Circle(P[1],0);
for(Re i=2;i<=n;++i)if(!PIC(C,P[i])){
C=Circle(P[i],0);
for(Re j=1;j<i;++j)if(!PIC(C,P[j])){
C.O=(P[i]+P[j])*0.5,C.r=Len(P[j]-C.O);
for(Re k=1;k<j;++k)if(!PIC(C,P[k]))C=getcircle(P[i],P[j],P[k]);
}
}
return C;
}
/*3.【三角剖分】*/
inline LD calc(Point A,Point B,Point O,LD R){//【三角剖分】
if(A==O||B==O)return 0;
Re op=dcmp(Cro(A-O,B-O))>0?1:-1;LD ans=0;
Vector x=A-O,y=B-O;
Re flag1=dcmp(Len(x)-R)>0,flag2=dcmp(Len(y)-R)>0;
if(!flag1&&!flag2)ans=Abs(Cro(A-O,B-O))/2.0;//两个点都在里面
else if(flag1&&flag2){//两个点都在外面
if(dcmp(dis_PL(O,A,B)-R)>=0)ans=R*R*Angle(x,y)/2.0;//完全包含了圆弧
else{//分三段处理 △+圆弧+△
if(dcmp(Cro(A-O,B-O))>0)swap(A,B);//把A换到左边
Point F=FootPoint(O,A,B);LD lenx=Len(F-O),len=sqrt(R*R-lenx*lenx);
Vector z=turn_P(F-O,Pi/2.0)*(len/lenx);Point B_=F+z,A_=F-z;
ans=R*R*(Angle(A-O,A_-O)+Angle(B-O,B_-O))/2.0+Cro(B_-O,A_-O)/2.0;
}
}
else{//一个点在里面,一个点在外面
if(flag1)swap(A,B);//使A为里面的点,B为外面的点
Point F=FootPoint(O,A,B);LD lenx=Len(F-O),len=sqrt(R*R-lenx*lenx);
Vector z=turn_P(F-O,Pi/2.0)*(len/lenx);Point C=dcmp(Cro(A-O,B-O))>0?F-z:F+z;
ans=Abs(Cro(A-O,C-O))/2.0+R*R*Angle(C-O,B-O)/2.0;
}
return ans*op;
}
}
using GEO::Point;
int n, m, x, y; Point a[1009], b[1009], c[1000009];
int main()
{
read(n);
For(i, 1, n) read(x, y), a[i] = Point(x, y);
read(m);
For(i, 1, m) read(x, y), b[i] = Point(x, y);
For(i, 1, n) For(j, 1, m) c[i * m - m + j] = b[j] - a[i];
auto ans = GEO::Min_Circle(c, n * m);
cout << fixed << setprecision(11) << ans.r << ' ' << ans.O.x << ' ' << ans.O.y << '\n';
return 0;
}
// 想上GM捏 想上GM捏 想上GM捏 想上GM捏 想上GM捏
// 伊娜可爱捏 伊娜贴贴捏
这程序好像有点Bug,我给组数据试试?
詳細信息
Test #1:
score: 100
Accepted
time: 15ms
memory: 92588kb
input:
3 1 5 2 4 6 8 2 1 3 1 6
output:
4.03112887415 -3.00000000000 -1.50000000000
result:
ok n=3 m=2 err=0.000000
Test #2:
score: 0
Accepted
time: 17ms
memory: 92524kb
input:
1 5 1 1 4 9
output:
0.00000000000 -1.00000000000 8.00000000000
result:
ok n=1 m=1 err=0.000000
Test #3:
score: 0
Accepted
time: 22ms
memory: 92456kb
input:
1 2 2 1 10 3
output:
0.00000000000 8.00000000000 1.00000000000
result:
ok n=1 m=1 err=0.000000
Test #4:
score: 0
Accepted
time: 21ms
memory: 92524kb
input:
1 1 2 1 1 2
output:
0.00000000000 0.00000000000 0.00000000000
result:
ok n=1 m=1 err=0.000000
Test #5:
score: 0
Accepted
time: 7ms
memory: 92556kb
input:
5 1 6 2 10 5 2 6 10 7 10 1 6 5
output:
4.40347873845 1.50000000000 -1.37500000000
result:
ok n=5 m=1 err=0.000000
Test #6:
score: 0
Accepted
time: 0ms
memory: 92552kb
input:
1 7 3 6 2 9 7 6 4 1 8 8 3 9 1 9
output:
4.59512410489 -2.91509433962 2.59433962264
result:
ok n=1 m=6 err=0.000000
Test #7:
score: 0
Accepted
time: 20ms
memory: 92596kb
input:
2 2 3 9 9 2 4 1 8 10
output:
9.30053761887 0.50000000000 -0.50000000000
result:
ok n=2 m=2 err=0.000000
Test #8:
score: 0
Accepted
time: 11ms
memory: 92556kb
input:
1 9 8 8 10 6 6 8 3 4 10 9 5 7 2 7 5 3 5 10
output:
4.31386919779 -2.69230769231 -1.23076923077
result:
ok n=1 m=8 err=0.000000
Test #9:
score: 0
Accepted
time: 8ms
memory: 92592kb
input:
3 7 3 4 9 7 1 1 6 2
output:
4.27200187266 0.50000000000 -3.00000000000
result:
ok n=3 m=1 err=0.000000
Test #10:
score: 0
Accepted
time: 16ms
memory: 92548kb
input:
2 6 8 8 8 1 4 3
output:
1.00000000000 -3.00000000000 -5.00000000000
result:
ok n=2 m=1 err=0.000000
Test #11:
score: 0
Accepted
time: 22ms
memory: 92552kb
input:
1 2 3 11 7 6 5 10 2 2 4 1 9 3 7 4 1 3 5 6 3 1 9 9 1 1
output:
5.65685424949 3.00000000000 2.00000000000
result:
ok n=1 m=11 err=0.000000
Test #12:
score: 0
Accepted
time: 12ms
memory: 92592kb
input:
11 7 4 5 1 7 3 9 10 3 1 10 10 5 5 10 5 5 6 4 1 10 4 1 8 10
output:
5.70087712550 1.50000000000 4.50000000000
result:
ok n=11 m=1 err=0.000000
Test #13:
score: 0
Accepted
time: 12ms
memory: 92556kb
input:
9 8 8 3 1 6 5 5 6 9 6 9 2 9 3 9 10 3 4 11 2 8 1 2 6 7 1 6 4 1 4 5 1 7 10 2 9 8 10 9 6 2
output:
10.96585609973 -0.50000000000 0.00000000000
result:
ok n=9 m=11 err=0.000000
Test #14:
score: 0
Accepted
time: 12ms
memory: 92588kb
input:
1 8 9 5 8 2 9 7 10 6 3 10 8 1
output:
5.14781507049 -2.50000000000 -3.50000000000
result:
ok n=1 m=5 err=0.000000
Test #15:
score: 0
Accepted
time: 7ms
memory: 92592kb
input:
1 2 5 3 6 10 6 5 5 5
output:
2.54950975680 3.50000000000 2.50000000000
result:
ok n=1 m=3 err=0.000000
Test #16:
score: 0
Accepted
time: 11ms
memory: 92564kb
input:
8 3 9 5 9 8 2 3 2 2 3 6 10 2 5 8 4 2 6 1 2 8
output:
8.32165848855 -1.50000000000 -1.00000000000
result:
ok n=8 m=2 err=0.000000
Test #17:
score: 0
Accepted
time: 4ms
memory: 92556kb
input:
96 499494 995347 917205 115724 615677 485675 26653 628830 290255 636019 436997 310488 679704 554538 836274 957304 523167 839393 156311 171726 69930 651786 817224 146624 576446 502999 448250 62722 233665 306365 158866 262089 119321 739022 740724 416112 447595 593338 896009 396447 197000 643460 732359...
output:
1237916.27993537697 -44154.23339819574 -45820.20369020559
result:
ok n=96 m=85 err=0.000000
Test #18:
score: 0
Accepted
time: 15ms
memory: 92460kb
input:
99 257522 959200 592396 748566 183664 7040 814688 14427 587861 749501 257013 647974 574312 16452 303911 801221 273835 163180 320884 988776 240807 795947 942562 731067 373821 953920 143172 74694 539481 15429 684143 403399 387168 771412 46522 597152 511683 147921 958389 1583 942733 714163 774789 32821...
output:
1288871.16778142337 -29975.50000000000 -9263.00000000000
result:
ok n=99 m=92 err=0.000000
Test #19:
score: 0
Accepted
time: 15ms
memory: 92616kb
input:
100 987841 173526 177982 166740 549515 522092 384826 507690 101387 672150 49976 800615 263841 244885 317357 360030 83752 360207 52473 896219 93778 10715 492695 855171 736451 599872 1405 199234 260020 787483 480774 125801 846063 137442 730974 808875 4697 513596 734335 772872 741817 525484 249698 1474...
output:
1212182.43911250528 57834.08674358403 25727.07544253068
result:
ok n=100 m=96 err=0.000000
Test #20:
score: 0
Accepted
time: 12ms
memory: 92596kb
input:
100 2100 493261 2232 480924 2363 513583 4231 526960 5996 428721 7499 412811 9989 390221 14718 367273 19269 350934 34370 302009 36805 295415 75680 204256 83177 188051 84259 186130 88584 543060 92807 572895 100939 609000 101502 163596 101936 613024 105050 624874 108584 156500 109230 638827 111400 1537...
output:
1032223.02490716102 58026.19226508812 20246.69109833946
result:
ok n=100 m=83 err=0.000000
Test #21:
score: 0
Accepted
time: 12ms
memory: 92656kb
input:
66 95860 272900 97306 254938 117654 220167 131357 199036 150957 318785 151093 362911 152746 380860 155133 169263 158495 427838 167614 471428 173305 494093 186930 517242 188000 142329 197122 532864 205961 899507 230549 551919 233463 928587 237597 102501 254306 999332 259764 557400 263409 558031 26877...
output:
987761.97199945393 224225.00000000000 -21726.50000000000
result:
ok n=66 m=100 err=0.000000
Test #22:
score: 0
Accepted
time: 18ms
memory: 92528kb
input:
98 23339 492481 89014 480660 89041 432908 90903 386255 91839 377309 134955 357101 140159 546249 140713 575042 170884 602523 172201 282212 196218 882407 200781 903891 202717 911224 203781 619304 208527 929437 209385 931430 209829 219728 214483 940179 216525 157708 221247 951565 222331 626997 225762 9...
output:
1000001.38194524936 -16724.78256427830 4967.85406119355
result:
ok n=98 m=99 err=0.000000
Test #23:
score: 0
Accepted
time: 15ms
memory: 92588kb
input:
88 25877 687813 31632 702872 50292 749437 58777 768460 60926 312678 61187 346434 62171 298892 63334 289745 67208 402050 73088 451930 75449 258737 77118 482674 77152 806056 81712 515955 83815 238185 84163 819202 92870 588484 98801 622179 106497 853280 111544 669489 112605 179371 114699 863818 133030 ...
output:
1012119.11881057440 -147183.60958249256 8191.84224334278
result:
ok n=88 m=91 err=0.000000
Test #24:
score: 0
Accepted
time: 15ms
memory: 92616kb
input:
77 303632 539543 304231 548535 306013 483196 307296 571896 307669 478206 309536 575990 313039 102618 317759 94854 321820 596009 335628 618096 344252 66009 354055 293491 360439 57058 361107 141696 363089 634276 366149 635865 379856 421457 382611 45803 384214 385713 386625 448925 402881 653417 410695 ...
output:
1043521.24206793697 -157896.39294954702 65902.50284577366
result:
ok n=77 m=80 err=0.000000
Test #25:
score: 0
Accepted
time: 16ms
memory: 92604kb
input:
97 2794 362191 4147 399220 4454 349686 6130 432943 6717 333182 6763 112567 10800 107497 12057 458770 18182 481566 22445 286502 22713 93363 28176 504839 31887 265270 35243 516538 38731 76253 49895 242059 51365 64668 64528 55827 67950 566520 79806 583152 84049 44162 90265 594464 111249 33641 122377 62...
output:
993406.36177826041 20325.88960076998 8484.77877817052
result:
ok n=97 m=66 err=0.000000
Test #26:
score: 0
Accepted
time: 21ms
memory: 92592kb
input:
89 47942 182627 55836 169685 66878 154453 76686 141108 84417 131462 101401 112835 105496 109507 127132 395883 127138 419676 128075 475215 129083 503243 129988 363220 130044 526666 131560 535537 133757 331768 134256 549340 135613 94546 145931 599346 148304 254635 155338 629736 162849 229793 163518 65...
output:
1117550.71585252899 13481.50000000000 1764.50000000000
result:
ok n=89 m=97 err=0.000000
Test #27:
score: 0
Accepted
time: 22ms
memory: 92676kb
input:
98 16284 502642 16633 493430 17800 515105 22765 550870 28059 586648 36346 613844 50719 638074 70086 456050 79472 684155 97022 711165 103050 336448 104891 383989 104938 723128 105132 311455 109161 443923 111816 251085 117512 740938 128560 188633 142349 159709 151508 142130 151783 785286 164551 800156...
output:
1023187.68441481844 21894.86919316593 21493.23893595838
result:
ok n=98 m=92 err=0.000000
Test #28:
score: 0
Accepted
time: 14ms
memory: 92464kb
input:
97 174144 365544 175753 338535 176411 390960 179994 299289 180147 426730 182463 290428 184873 468930 191401 520692 193260 535025 195371 246795 198343 554865 204761 578268 209835 589959 212303 595491 213329 220953 220160 612606 220241 211257 224517 617663 261610 164554 280034 145374 298974 669061 307...
output:
1014748.12439221454 -79822.82769343484 26708.19044272220
result:
ok n=97 m=96 err=0.000000
Test #29:
score: 0
Accepted
time: 8ms
memory: 92604kb
input:
95 98065 636830 103777 691006 113633 747583 127257 805793 133097 829409 139376 847000 145099 859891 174956 919356 179338 585491 180375 929035 188474 609821 204919 950405 208035 447744 217023 956198 242307 968209 244358 475478 252142 566321 264197 412819 276158 981100 280280 982412 284393 983205 3014...
output:
1027711.16079461811 11106.51914834121 5712.60236353654
result:
ok n=95 m=95 err=0.000000
Test #30:
score: 0
Accepted
time: 54ms
memory: 92576kb
input:
996 499494 995347 917205 115724 615677 485675 26653 628830 290255 636019 436997 310488 679704 554538 836274 957304 523167 839393 156311 171726 69930 651786 817224 146624 576446 502999 448250 62722 233665 306365 158866 262089 119321 739022 740724 416112 447595 593338 896009 396447 197000 643460 73235...
output:
1352561.66275852626 18438.40799460773 -25.17113807255
result:
ok n=996 m=985 err=0.000000
Test #31:
score: 0
Accepted
time: 48ms
memory: 92584kb
input:
999 257522 959200 592396 748566 183664 7040 814688 14427 587861 749501 257013 647974 574312 16452 303911 801221 273835 163180 320884 988776 240807 795947 942562 731067 373821 953920 143172 74694 539481 15429 684143 403399 387168 771412 46522 597152 511683 147921 958389 1583 942733 714163 774789 3282...
output:
1378487.82490125752 2843.00000000000 5770.00000000000
result:
ok n=999 m=992 err=0.000000
Test #32:
score: 0
Accepted
time: 34ms
memory: 92580kb
input:
993 615 519218 617 517469 619 515767 624 524431 626 525094 630 513100 642 527669 660 508605 660 529253 685 531414 730 499678 762 536468 779 537073 816 493023 842 491073 875 489905 927 488312 950 541893 1117 482527 1206 547427 1264 478680 1490 473007 1514 553162 1552 471495 1796 558255 1799 466169 18...
output:
1062252.79452922094 4452.25150732914 -12326.78957162130
result:
ok n=993 m=976 err=0.000000
Test #33:
score: 0
Accepted
time: 53ms
memory: 92492kb
input:
981 1017 566234 1019 563943 1020 567032 1023 559536 1043 557326 1061 555877 1082 554710 1082 572289 1125 552838 1140 577041 1182 550439 1237 548237 1237 582678 1308 546219 1326 586146 1388 544028 1463 590551 1535 540215 1577 594018 1640 537506 1833 532998 1882 531924 1963 603078 2143 607114 2165 526...
output:
1079230.20077716505 7723.73863763874 -10971.60098826279
result:
ok n=981 m=990 err=0.000000
Test #34:
score: 0
Accepted
time: 53ms
memory: 92584kb
input:
972 1349 512364 1364 516711 1379 504982 1380 518796 1420 499424 1423 523276 1427 523682 1435 497837 1442 524561 1523 489993 1538 530105 1631 483721 1639 534802 1672 535964 1736 479419 1835 475666 1879 540869 1957 471546 1963 542804 2053 468665 2088 545588 2169 466450 2256 464959 2621 459302 2840 456...
output:
1074931.55438590601 7678.50000000000 2282.50000000000
result:
ok n=972 m=969 err=0.000000
Test #35:
score: 0
Accepted
time: 50ms
memory: 92568kb
input:
1000 164 534631 166 533532 189 527791 212 537500 221 525573 299 542342 348 544665 367 518493 441 515154 491 551253 514 512559 589 555378 647 508575 774 561637 919 566166 934 501125 1205 573809 1259 493586 1476 488568 1559 486663 1612 485603 1625 584283 1852 589866 1938 479997 2063 594624 2139 476569...
output:
1081453.23508878552 5571.00000000000 -1776.00000000000
result:
ok n=1000 m=998 err=0.000000
Test #36:
score: 0
Accepted
time: 48ms
memory: 92576kb
input:
994 631 442590 641 444412 644 439051 686 450632 687 431990 699 430187 706 429189 728 452731 757 422171 771 420270 822 416597 843 457792 861 414434 881 459362 910 460435 967 410702 1043 465018 1049 408220 1198 470104 1212 403386 1311 401186 1320 474050 1346 474797 1444 477359 1483 397515 1518 396784 ...
output:
1054401.72944967034 -6981.94484394909 -6433.85302241189
result:
ok n=994 m=996 err=0.000000
Test #37:
score: 0
Accepted
time: 47ms
memory: 92584kb
input:
991 1850 564831 1852 562297 1855 559736 1872 557599 1876 569480 1967 549168 1982 573517 2012 574537 2034 544935 2080 542038 2104 577105 2223 535854 2469 525460 2509 523828 2529 523133 2615 590300 2668 591588 2674 518694 2683 518423 2739 516933 2856 595782 2875 513379 3026 510561 3182 602250 3238 507...
output:
1060980.93806138658 8294.00492296561 -6497.23304009625
result:
ok n=991 m=995 err=0.000000
Test #38:
score: 0
Accepted
time: 56ms
memory: 92624kb
input:
994 425 477653 426 481113 427 472213 430 482938 434 484599 437 485348 441 486079 486 490258 489 466458 534 493880 603 459742 614 499472 651 457772 681 503775 705 455761 762 508666 876 449933 997 517849 1051 445577 1089 521053 1128 443937 1168 523373 1212 524660 1225 442009 1422 529769 1497 531584 19...
output:
1082267.45544306992 -1421.63566833730 14387.42195584418
result:
ok n=994 m=994 err=0.000000
Test #39:
score: 0
Accepted
time: 42ms
memory: 92620kb
input:
991 1164 448671 1172 446635 1180 445056 1183 451382 1184 444270 1225 456408 1235 457554 1238 438265 1247 458200 1312 430347 1345 462205 1366 425285 1416 420916 1450 418161 1527 412566 1608 406816 1648 404489 1689 402226 1716 476811 1752 478195 1929 484629 1953 394091 2074 488972 2087 390190 2125 490...
output:
1072254.61133538614 17892.00000000000 -7286.00000000000
result:
ok n=991 m=1000 err=0.000000
Test #40:
score: 0
Accepted
time: 62ms
memory: 92624kb
input:
989 1041 516925 1043 521187 1046 522648 1050 515202 1055 514689 1081 535143 1098 539942 1127 547011 1139 548732 1170 552696 1257 563452 1278 495918 1280 566051 1295 494496 1316 568966 1360 489985 1368 572937 1435 484947 1517 479665 1525 479171 1535 582555 1553 477552 1588 475994 1603 584808 1756 589...
output:
1071350.16165455914 11952.50000000000 4381.00000000000
result:
ok n=989 m=992 err=0.000000
Test #41:
score: 0
Accepted
time: 77ms
memory: 92576kb
input:
1000 1195 462128 1201 463009 1234 457015 1237 456705 1249 466226 1269 454141 1285 468002 1329 449635 1334 469813 1347 470254 1352 448262 1392 446152 1447 473533 1485 443138 1496 475073 1535 476212 1587 477569 1755 436423 1755 481897 1782 435783 1849 484151 2011 430504 2052 429700 2060 489009 2077 48...
output:
1056333.78573878030 4025.55327848846 3532.07462409410
result:
ok n=1000 m=991 err=0.000000
Test #42:
score: 0
Accepted
time: 47ms
memory: 92624kb
input:
993 614 483119 615 482738 651 478578 710 473392 717 497183 738 499968 763 470294 829 509584 836 466495 881 513317 903 463452 912 515293 985 518319 1055 521174 1087 522385 1138 453322 1151 524359 1171 452247 1298 448166 1418 444353 1469 442962 1555 440623 1633 438708 1804 434526 1821 434159 1923 4322...
output:
1075574.38650258128 7087.80568674703 4861.12892616092
result:
ok n=993 m=994 err=0.000000
Test #43:
score: 0
Accepted
time: 55ms
memory: 92716kb
input:
997 75 449509 76 446631 78 450295 95 432993 109 456855 125 458612 152 461005 184 463086 207 464565 228 423968 231 465884 255 423079 342 421238 355 471781 406 474202 412 474480 480 476787 696 414429 906 490192 1020 493693 1040 408413 1063 494968 1201 498932 1344 502970 1399 504512 1546 508208 1624 39...
output:
1071140.64965616220 3538.08364279320 3842.17600763180
result:
ok n=997 m=997 err=0.000000
Test #44:
score: 0
Accepted
time: 55ms
memory: 92580kb
input:
989 459 533612 460 526411 462 541026 464 522019 470 549472 473 549914 479 518626 493 516263 524 511559 550 508138 563 507308 572 506895 597 559114 633 561642 721 500997 732 565245 804 567350 805 498117 894 495241 1043 573673 1146 576117 1185 486712 1227 485630 1384 580969 1537 479019 1788 473674 186...
output:
1060385.32755179337 4035.97993104926 -2002.21621449948
result:
ok n=989 m=996 err=0.000000
Test #45:
score: 0
Accepted
time: 57ms
memory: 92616kb
input:
997 1316 518316 1322 521512 1325 508449 1343 505459 1346 526415 1365 502360 1365 529214 1382 499983 1392 498868 1432 496132 1475 493712 1495 539863 1516 491426 1580 544084 1635 546558 1669 483232 1684 547717 1713 481004 1751 479253 1832 476553 1973 473579 2087 556581 2175 469575 2238 468498 2420 465...
output:
1070746.73966582779 15036.00000000000 3623.00000000000
result:
ok n=997 m=999 err=0.000000
Test #46:
score: 0
Accepted
time: 48ms
memory: 92440kb
input:
994 2205 552253 2206 552689 2209 552951 2215 548753 2259 543640 2274 542257 2357 539254 2374 561411 2427 563387 2513 566395 2548 532374 2602 569239 2624 569935 2656 528952 2811 524516 2861 523164 2884 577414 2910 578134 2962 579377 3067 517953 3070 581791 3188 584059 3189 514970 3302 586224 3505 589...
output:
1069818.05367184841 13613.35982782062 -1991.94366434622
result:
ok n=994 m=999 err=0.000000
Test #47:
score: 0
Accepted
time: 53ms
memory: 92800kb
input:
963 834 543361 836 535792 849 552072 850 552501 874 531035 883 556864 888 557488 914 560360 930 561193 935 527487 1037 524408 1240 577124 1244 518226 1280 578701 1319 516158 1439 583355 1462 512721 1525 511304 1584 587278 1608 509538 1817 592099 1828 505026 1948 594421 2073 596472 2134 498784 2135 5...
output:
1064784.73614964766 2330.39517099106 7032.76207084154
result:
ok n=963 m=993 err=0.000000
Test #48:
score: 0
Accepted
time: 79ms
memory: 92588kb
input:
985 2582 537826 2618 542713 2624 531735 2651 528037 2673 525287 2751 519638 2816 515139 2898 510087 2954 554627 3019 503015 3098 558595 3109 558889 3123 497277 3155 559944 3321 487951 3479 480516 3583 476304 3636 474522 3636 569898 3700 472612 3896 467080 3942 465895 3960 576596 4113 461584 4209 581...
output:
1069365.25385729188 -3085.07195017484 10396.21136461483
result:
ok n=985 m=997 err=0.000000
Test #49:
score: 0
Accepted
time: 56ms
memory: 92660kb
input:
987 1181 498215 1183 500828 1194 494762 1202 506979 1212 508963 1252 514679 1296 487535 1299 487332 1312 486465 1339 524535 1361 526912 1373 527965 1398 529760 1444 479976 1444 532681 1507 536063 1530 536924 1556 474716 1868 548605 2021 553300 2034 455842 2147 556616 2234 558875 2262 449370 2294 560...
output:
1074840.58267308097 12125.72313247729 13972.04666307748
result:
ok n=987 m=990 err=0.000000
Test #50:
score: 0
Accepted
time: 16ms
memory: 92596kb
input:
3 15 4 3 4 19 16 2 9 15 15 15
output:
12.52996408614 1.00000000000 5.00000000000
result:
ok n=3 m=2 err=0.000000
Test #51:
score: 0
Accepted
time: 8ms
memory: 92464kb
input:
14 9 1 10 1 7 20 10 16 14 5 17 4 7 12 20 13 1 3 20 17 7 10 6 1 6 15 11 11 4 4 13 20 13 16 13 15 13
output:
18.84807682497 1.50000000000 3.00000000000
result:
ok n=14 m=4 err=0.000000
Extra Test:
score: 0
Extra Test Passed