QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#916931#9728. Catch the StarJose_17AC ✓1348ms52148kbC++1417.9kb2025-02-27 02:21:282025-02-27 02:21:28

Judging History

This is the latest submission verdict.

  • [2025-02-27 02:21:28]
  • Judged
  • Verdict: AC
  • Time: 1348ms
  • Memory: 52148kb
  • [2025-02-27 02:21:28]
  • Submitted

answer

#include <bits/stdc++.h>
using namespace std;
 
// Holi c:
 
//#define ll long long int
#define ii __int128
#define fi first
#define se second
#define pb push_back
#define all(v) v.begin(), v.end()

typedef long long int ll; 
 
const int Inf = 2e9;
const int Inf2 = 2e9 + 1;
const ll mod = 1e9+7;
const ll INF = 4e18;
const ll INF2 = 1e10 + 1;
 
using ld = long double;

const ld eps = 1e-9, inf = numeric_limits<ld>::max(), pi = acos(-1);

bool geq(ld a, ld b){return a-b >= -eps;}     
bool leq(ld a, ld b){return b-a >= -eps;}     
bool ge(ld a, ld b){return a-b > eps;}        
bool le(ld a, ld b){return b-a > eps;}       
bool eq(ld a, ld b){return abs(a-b) <= eps;}
bool neq(ld a, ld b){return abs(a-b) > eps;} 

struct fraccion{
	ll num, den;
	fraccion(){
		num = 0, den = 1;
	}
	fraccion(ll x, ll y){
		if(y < 0)
			x *= -1, y *=-1;
		ll d = __gcd(abs(x), abs(y));
		num = x/d, den = y/d;
	}
	fraccion(ll v){
		num = v;
		den = 1;
	}
	fraccion operator+(const fraccion& f) const{
		ll d = __gcd(den, f.den);
		return fraccion(num*(f.den/d) + f.num*(den/d), den*(f.den/d));
	}
	fraccion operator-() const{
		return fraccion(-num, den);
	}
	fraccion operator-(const fraccion& f) const{
		return *this + (-f);
	}
	fraccion operator*(const fraccion& f) const{
		return fraccion(num*f.num, den*f.den);
	}
	fraccion operator/(const fraccion& f) const{
		return fraccion(num*f.den, den*f.num);
	}
	fraccion operator+=(const fraccion& f){
		*this = *this + f;
		return *this;
	}
	fraccion operator-=(const fraccion& f){
		*this = *this - f;
		return *this;
	}
	fraccion operator++(int xd){
		*this = *this + 1;
		return *this;
	}
	fraccion operator--(int xd){
		*this = *this - 1;
		return *this;
	}
	fraccion operator*=(const fraccion& f){
		*this = *this * f;
		return *this;
	}
	fraccion operator/=(const fraccion& f){
		*this = *this / f;
		return *this;
	}
	bool operator==(const fraccion& f) const{
		ll d = __gcd(den, f.den);
		return (ii)((ii)num*(f.den/d) == (ii)((ii)den/d)*f.num);
	}
	bool operator!=(const fraccion& f) const{
		ll d = __gcd(den, f.den);
		return (ii)((ii)num*(f.den/d) != (ii)((ii)den/d)*f.num);
	}
	bool operator >(const fraccion& f) const{
		ll d = __gcd(den, f.den);
		return (ii)((ii)num*(f.den/d) > (ii)((ii)den/d)*f.num);
	}
	bool operator <(const fraccion& f) const{
		ll d = __gcd(den, f.den);
		return (ii)((ii)num*(f.den/d) < (ii)((ii)den/d)*f.num);
	}
	bool operator >=(const fraccion& f) const{
		ll d = __gcd(den, f.den);
		return (ii)((ii)num*(f.den/d) >= (ii)((ii)den/d)*f.num);
	}
	bool operator <=(const fraccion& f) const{
		ll d = __gcd(den, f.den);
		return (ii)((ii)num*(f.den/d) <= (ii)((ii)den/d)*f.num);
	}
	fraccion inverso() const{
		return fraccion(den, num);
	}
	fraccion fabs() const{
		fraccion nueva;
		nueva.num = abs(num);
		nueva.den = den;
		return nueva;
	}
	long double value() const{
		return (long double)num / (long double)den;
	}
};

bool geqf(fraccion a, fraccion b){return a >= b;}
bool leqf(fraccion a, fraccion b){return a <= b;}
bool gef(fraccion a, fraccion b){return a > b;}
bool lef(fraccion a, fraccion b){return a < b;}
bool eqf(fraccion a, fraccion b){return a == b;}
bool neqf(fraccion a, fraccion b){return a != b;}

struct point{
	ld x, y;
	point(): x(0), y(0){}
	point(ld x, ld y): x(x), y(y){}

	point operator+(const point & p) const{return point(x + p.x, y + p.y);}
	point operator-(const point & p) const{return point(x - p.x, y - p.y);}
	point operator*(const ld & k) const{return point(x * k, y * k);}
	point operator/(const ld & k) const{return point(x / k, y / k);}

	point perp() const{return point(-y, x);}
	ld dot(const point & p) const{return x * p.x + y * p.y;}
	ld cross(const point & p) const{return x * p.y - y * p.x;}
	ld norm() const{return x * x + y * y;}
	ld length() const{return sqrtl(x * x + y * y);}
	point unit() const{return (*this) / length();}

	bool operator==(const point & p) const{return eq(x, p.x) && eq(y, p.y);}
	bool operator!=(const point & p) const{return !(*this == p);}
	bool operator<(const point & p) const{return le(x, p.x) || (eq(x, p.x) && le(y, p.y));}
	bool operator>(const point & p) const{return ge(x, p.x) || (eq(x, p.x) && ge(y, p.y));}
};

istream &operator>>(istream &is, point & p){return is >> p.x >> p.y;}
ostream &operator<<(ostream &os, const point & p){return os << "(" << p.x << ", " << p.y << ")";}

struct pointf {
    fraccion x, y;
    pointf(): x(fraccion()), y(fraccion()) {}
    pointf(fraccion x, fraccion y): x(x), y(y) {}

    pointf operator+(const pointf & p) const{return pointf(x + p.x, y + p.y);}
    pointf operator-(const pointf & p) const{return pointf(x - p.x, y - p.y);}
    pointf operator*(const fraccion & k) const{return pointf(x * k, y * k);}
    pointf operator/(const fraccion & k) const{return pointf(x / k, y / k);}
    
    pointf operator+=(const pointf & p){*this = *this + p; return *this;}
    pointf operator-=(const pointf & p){*this = *this - p; return *this;}
    pointf operator*=(const fraccion & p){*this = *this * p; return *this;}
    pointf operator/=(const fraccion & p){*this = *this / p; return *this;}

    fraccion dot(const pointf & p) const{return x * p.x + y * p.y;}
    fraccion cross(const pointf & p) const{return x * p.y - y * p.x;}
    fraccion norm() const{return x + y;}

    bool operator==(const pointf & p) const{return eqf(x, p.x) && eqf(y, p.y);}
    bool operator!=(const pointf & p) const{return !(*this == p);}
    bool operator<(const pointf & p) const{return lef(x, p.x) || (eqf(x, p.x) && lef(y, p.y));}
    bool operator>(const pointf & p) const{return gef(x, p.x) || (eqf(x, p.x) && gef(y, p.y));}
};

int sgn(ld x){
	if(ge(x, 0)) return 1;
	if(le(x, 0)) return -1;
	return 0;
}

vector<point> convexHull(vector<point> P){
	sort(P.begin(), P.end());
	vector<point> L, U;
	for(int i = 0; i < P.size(); i++){
		while(L.size() >= 2 && leq((L[L.size() - 2] - P[i]).cross(L[L.size() - 1] - P[i]), 0)){
			L.pop_back();
		}
		L.push_back(P[i]);
	}
	for(int i = P.size() - 1; i >= 0; i--){
		while(U.size() >= 2 && leq((U[U.size() - 2] - P[i]).cross(U[U.size() - 1] - P[i]), 0)){
			U.pop_back();
		}
		U.push_back(P[i]);
	}
	L.pop_back();
	U.pop_back();
	L.insert(L.end(), U.begin(), U.end());
	return L;
}

vector<vector<point>> twoSidesCH(vector<point> P){
	sort(P.begin(), P.end());
	vector<vector<point>> L;
	vector<point> U;
	for(int i = 0; i < P.size(); i++){
		while(U.size() >= 2 && leq((U[U.size() - 2] - P[i]).cross(U[U.size() - 1] - P[i]), 0)){
			U.pop_back();
		}
		U.push_back(P[i]);
	}
	if(eq(U[U.size() - 1].x, U[U.size() - 2].x)) U.pop_back();
	L.pb(U);
	U.clear();
	for(int i = P.size() - 1; i >= 0; i--){
		while(U.size() >= 2 && leq((U[U.size() - 2] - P[i]).cross(U[U.size() - 1] - P[i]), 0)){
			U.pop_back();
		}
		U.push_back(P[i]);
	}
	reverse(all(U));
	if(eq(U[U.size() - 1].x, U[U.size() - 2].x)) U.pop_back();
	reverse(all(U));
	if(eq(U[U.size() - 1].x, U[U.size() - 2].x)) U.pop_back();
	L.pb(U);
	return L;
}

ld area(vector<point> & P){
	int n = P.size();
	ld ans = 0;
	for(int i = 0; i < n; i++){
		ans += P[i].cross(P[(i + 1) % n]);
	}
	return abs(ans / 2);
}

pointf intersectLinesf(const point & a1, const point & v1, const point & a2, const point & v2){
	fraccion det = v1.cross(v2);
	pointf b1(a1.x, a1.y), u1(v1.x, v1.y), b2(a2.x, a2.y), u2(v2.x, v2.y);
	return b1 + u1 * ((b2 - b1).cross(u2) / det);
}

point intersectLines(const point & a1, const point & v1, const point & a2, const point & v2){
	//lines a1+tv1, a2+tv2
	//assuming that they intersect
	ld det = v1.cross(v2);
	return a1 + v1 * ((a2 - a1).cross(v2) / det);
}

bool pointInLine(const point & a, const point & v, const point & p){
	return eq((p - a).cross(v), 0);
}

bool pointInSegment(const point & a, const point & b, const point & p){
	return pointInLine(a, b - a, p) && leq((a - p).dot(b - p), 0);
}

int intersectSegmentsInfo(const point & a, const point & b, const point & c, const point & d){
	//segment ab, segment cd
	point v1 = b - a, v2 = d - c;
	int t = sgn(v1.cross(c - a)), u = sgn(v1.cross(d - a));
	if(t == u){
		if(t == 0){
			if(pointInSegment(a, b, c) || pointInSegment(a, b, d) || pointInSegment(c, d, a) || pointInSegment(c, d, b)){
				return -1; //infinity points
			}else{
				return 0; //no point
			}
		}else{
			return 0; //no point
		}
	}else{
		return sgn(v2.cross(a - c)) != sgn(v2.cross(b - c)); //1: single point, 0: no point
	}
}

bool pointInPerimeter(const vector<point> & P, const point & p){
	int n = P.size();
	for(int i = 0; i < n; i++){
		if(pointInSegment(P[i], P[(i + 1) % n], p)){
			return true;
		}
	}
	return false;
}

bool crossesRay(const point & a, const point & b, const point & p){
	return (geq(b.y, p.y) - geq(a.y, p.y)) * sgn((a - p).cross(b - p)) > 0;
}

int pointInPolygon(const vector<point> & P, const point & p){
	if(pointInPerimeter(P, p)){
		return 1;
	}
	int n = P.size();
	int rays = 0;
	for(int i = 0; i < n; i++){
		rays += crossesRay(P[i], P[(i + 1) % n], p);
	}
	return rays & 1;
}

int intersectLineSegmentInfo(const point & a, const point & v, const point & c, const point & d){
	//line a+tv, segment cd
	point v2 = d - c;
	ld det = v.cross(v2);
	if(eq(det, 0)){
		if(eq((c - a).cross(v), 0)){
			return -1; //infinity points
		}else{
			return 0; //no point
		}
	}else{
		return sgn(v.cross(c - a)) != sgn(v.cross(d - a)); //1: single point, 0: no point
	}
}

vector<point> cutPolygon(const vector<point> & P, const point & a, const point & v){
	//returns the part of the convex polygon P on the left side of line a+tv
	int n = P.size();
	vector<point> lhs;
	for(int i = 0; i < n; ++i){
		if(geq(v.cross(P[i] - a), 0)){
			lhs.push_back(P[i]);
		}
		if(intersectLineSegmentInfo(a, v, P[i], P[(i+1)%n]) == 1){
			point p = intersectLines(a, v, P[i], P[(i+1)%n] - P[i]);
			if(p != P[i] && p != P[(i+1)%n]){
				lhs.push_back(p);
			}
		}
	}
	return lhs;
}

vector<point> tangentsPointPolygon(const vector<point> & P, const vector<vector<point>> & Ps, const point & p){
	int n = P.size(), m = Ps[0].size(), k = Ps[1].size();
	
	int lk = m; if(Ps[0][m - 1] == Ps[1][0]) lk--; 

	auto tang = [&](int l, int r, ld w, int kl) -> int {
		int res = min(l, r);
        while(l <= r){
            int m = (l + r) / 2;
			ld a = (P[(m + kl) % n] - p).cross(P[(m + 1 + kl) % n] - p) * w, b = (P[(m + kl) % n] - p).cross(P[(m - 1 + n + kl) % n] - p) * w;
			if(geq(a, 0) && geq(b, 0)) return m;
            if(geq(a, 0)) r = m - 1, res = m;
            else l = m + 1;
        }
        return res;
    };

	auto bs = [&](int l, int r, const vector<point> & A, ld w) -> int {
        int res = l;
        ld w1 = p.x * w;
        while(l <= r){
            int m = (l + r) / 2;
			if(ge(A[m].x * w, w1)) r = m - 1;
			else res = m, l = m + 1;
        }
        return res;
    };
    
	point left = p, rigth = p;

	int t1 = bs(0, m - 1, Ps[0], 1), t2 = bs(0, k - 1, Ps[1], -1);
	
	auto u1 = tang(0, t1, -1, 0), u2 = tang(0, t2, -1, lk);
	auto v1 = tang(t1, m - 1, 1, 0), v2 = tang(t2, k - 1, 1, lk);
	//if(p.x == P[t1].x) v1 = tang(t1, m - 1, 1, 0);
	//if(p.x == P[(lk + t2) % n].x) v2 = tang(t2, k - 1, 1, lk);
	
	if(leq((P[u1] - p).cross(P[(u1 - 1 + n) % n] - p), 0) && leq((P[u1] - p).cross(P[(u1 + 1) % n] - p), 0)) left = P[u1];
	else if(leq((P[(lk + u2) % n] - p).cross(P[(lk + u2 - 1 + n) % n] - p), 0) && leq((P[(lk + u2) % n] - p).cross(P[(lk + u2 + 1) % n] - p), 0)) left = P[(lk + u2) % n];
	
	if(geq((P[v1] - p).cross(P[(v1 - 1 + n) % n] - p), 0) && geq((P[v1] - p).cross(P[(v1 + 1) % n] - p), 0)) rigth = P[v1];
	else if(geq((P[(lk + v2) % n] - p).cross(P[(lk - 1 + n + v2) % n] - p), 0) && geq((P[(lk + v2) % n] - p).cross(P[(lk + 1 + v2) % n] - p), 0)) rigth = P[(lk + v2) % n];
    
	return {left, rigth};
}

vector<point> tangentsLineal(vector<point> A, point p){
    int iz = 0, dr = 0, n = A.size();
    for(int i = 0; i < n; i++){
        int at = i - 1, nx = i + 1;
        if(at < 0) at = n - 1; if(nx == n) nx = 0;
        if(leq((A[i] - p).cross(A[at] - p), 0) && leq((A[i] - p).cross(A[nx] - p), 0)) iz = i;
        if(geq((A[i] - p).cross(A[at] - p), 0) && geq((A[i] - p).cross(A[nx] - p), 0)) dr = i;
    }
    return {A[iz], A[dr]};
}

pair<fraccion, fraccion> calc(vector<point> & A, vector<point> B, vector<vector<point>> & tws, int l, int r){
    fraccion minx = Inf2, maxx = -Inf2;
    pointf x0(-Inf2, 0), x1(Inf2, 0);
    point s0(-Inf2, 0), s1(Inf2, 0);
    point w1(l, 0), w2(r, 0);
    int n = B.size();
    for(int i = 0; i < n; i++){
        auto u = intersectSegmentsInfo(B[i], B[(i + 1) % n], s0, s1);
        if(u == 1){
            auto p = intersectLinesf(B[i], B[(i + 1) % n] - B[i], s0, s1 - s0);
            //minx = min(minx, p.x); maxx = max(maxx, p.x);
        }else if(u == -1){
            //minx = min(minx, min(fraccion(B[i].x), fraccion(B[(i + 1) % n].x)));
            //maxx = max(maxx, max(fraccion(B[i].x), fraccion(B[(i + 1) % n].x)));
        }
    }
    point a1(1, 0);
    for(int i = 0; i < n; i++){
        auto ts = tangentsPointPolygon(A, tws, B[i]);
        point t1 = ts[0], t2 = ts[1];
        //cout<<B[i]<<" => "<<t1<<" & "<<t2<<'\n';
        if(neq(a1.cross(t1 - B[i]), 0)){
            auto p1 = intersectLinesf(B[i], t1 - B[i], point(0, 0), a1);
            auto p2 = intersectLines(B[i], t1 - B[i], point(0, 0), a1);
            bool pl = true;
			point p(p1.x.value(), p1.y.value());
            //cout<<p.x.value()<<" , "<<p.y.value()<<" | ";
            if(eq((p - t1).length(), (p - B[i]).length() + (B[i] - t1).length()) && pl){
                //cout<<"r";
                if(minx > p1.x) minx = p1.x; if(maxx < p1.x) maxx = p1.x;
                
            }
        }
        if(neq(a1.cross(t2 - B[i]), 0)){
            auto p1 = intersectLinesf(B[i], t2 - B[i], point(0, 0), a1);
            auto p2 = intersectLines(B[i], t2 - B[i], point(0, 0), a1);
            bool pl = true;
            point p(p1.x.value(), p1.y.value());
			//cout<<p.x.value()<<" , "<<p.y.value()<<'\n';
            if(eq((p - t2).length(), (p - B[i]).length() + (B[i] - t2).length()) && pl){
                //cout<<"r";
                if(minx > p1.x) minx = p1.x; if(maxx < p1.x) maxx = p1.x;
                
            }
        }
        
        //if(ge((t1 - B[i]).cross(w1 - B[i]), 0) && le((t2 - B[i]).cross(w1 - B[i]), 0)) minx = -Inf2;
        //if(ge((t1 - B[i]).cross(w2 - B[i]), 0) && le((t2 - B[i]).cross(w2 - B[i]), 0)) maxx = Inf2;
        
    }
    
    auto itg0 = tangentsPointPolygon(A, tws, w1);
    auto itg1 = tangentsLineal(B, w1);
    auto dtg0 = tangentsPointPolygon(A, tws, w2);
    auto dtg1 = tangentsLineal(B, w2);
    
    auto t0 = itg0[0], t1 = itg0[1], t2 = itg1[0], t3 = itg1[1];
    auto t4 = dtg0[0], t5 = dtg0[1], t6 = dtg1[0], t7 = dtg1[1];
    
    auto v = B;
    v = cutPolygon(v, w1, w1 - t0); v = cutPolygon(v, w1, t1 - w1); v = cutPolygon(v, t1, t0 - t1);
    
    if(area(v) > 0.0001){
        minx = -Inf2;
    }
    
    /*
        if(leq((t2 - w1).cross(t0 - w1), 0) && geq((t3 - w1).cross(t0 - w1), 0)) minx = -Inf2;
        if(leq((t2 - w1).cross(t1 - w1), 0) && geq((t3 - w1).cross(t1 - w1), 0)) minx = -Inf2;
        if(leq((t0 - w1).cross(t2 - w1), 0) && geq((t1 - w1).cross(t2 - w1), 0)) minx = -Inf2;
    */
    
    v = B;
    v = cutPolygon(v, w2, w2 - t4); v = cutPolygon(v, w2, t5 - w2); v = cutPolygon(v, t5, t4 - t5);
        
    if(area(v) > 0.0001){
        maxx = Inf2;
    }
    
    /*
        if(leq((t6 - w2).cross(t4 - w2), 0) && geq((t7 - w2).cross(t4 - w2), 0)) maxx = Inf2;
        if(leq((t6 - w2).cross(t5 - w2), 0) && geq((t7 - w2).cross(t5 - w2), 0)) maxx = Inf2;
        if(leq((t4 - w2).cross(t6 - w2), 0) && geq((t5 - w2).cross(t6 - w2), 0)) maxx = Inf2;
    */
    //cout<<minx.value()<<" "<<maxx.value()<<'\n';
    //if(minx == -Inf2 && maxx == Inf2) return {Inf2, Inf2};
    return {minx, maxx};
}

ld calc1(){
    int m, l, r; cin>>m>>l>>r;
    int n; cin>>n;
    vector<point> P(n);
    for(int i = 0; i < n; i++){
        int a, b; cin>>a>>b; P[i] = point(a, b);
    }
    vector<vector<point>> Moons;
    for(int i = 0; i < m; i++){
        int k; cin>>k; vector<point> aux;
        for(int j = 0; j < k; j++){
            int a, b; cin>>a>>b; aux.pb(point(a, b));
        }
        Moons.pb(aux);
    }
    
    P = convexHull(P);
	auto tws = twoSidesCH(P);
	//for(auto e : tws[1]) cout<<e<<" "; cout<<'\n';
	//for(auto e : tw) cout<<e<<" "; cout<<'\n';
    vector<pair<fraccion, fraccion>> Segs;
    for(int i = 0; i < m; i++){
        auto u = calc(P, Moons[i], tws, l , r);
        //cout<<'\n'<<"----------------------------------------"<<'\n';
        Segs.pb(u);
    }
    sort(all(Segs));
    //for(auto e : Segs) cout<<setprecision(15)<<e.fi.value()<<" , "<<e.se.value()<<" | "; cout<<'\n';
    //cout<<(fraccion(Segs[0].se) - fraccion(Segs[0].fi)).value()<<" ";
    ld ans = 0; fraccion ant(l); bool f = false;
    for(int i = 0; i < m; i++){
        if(Segs[i].fi > fraccion(r)){
            if(fraccion(r) > ant){
                f = true;
            }
            if(ant < fraccion(r)) ans += (fraccion(r).value() - ant.value());
            ant = r;
            break;
        }
        if(Segs[i].fi >= ant){
            if(!((Segs[i].fi == l && ant == l) || (Segs[i].fi == r && ant == r))) f = true; 
            //cout<<(Segs[i].fi - ant).value();
        }
        if(ant < Segs[i].fi) ans += abs(ant.value() - Segs[i].fi.value());
        ant = max(ant, Segs[i].se);
        //cout<<ans<<'\n';
    }
    if(ant < r) ans += (fraccion(r).value() - max(ant.value(), fraccion(l).value())), f = true;
    if(!f && ans == 0) return -1;
    return ans;
}

int main(){
    ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    int t; cin>>t;
    while(t--){
		auto p = calc1();
        cout<<setprecision(25)<<p<<'\n';
    }
}

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

詳細信息

Test #1:

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

input:

2
4 -8 8
3 -7 7 -6 8 -7 8
3 -9 -2 -7 3 -9 -1
3 -2 3 0 2 -4 5
3 5 1 5 3 4 2
3 1 -1 2 -2 3 -1
5 -8 8
5 -14 -3 -10 -2 -9 2 -10 4 -12 5
3 -16 0 -15 0 -15 1
3 -15 6 -9 5 -15 7
3 -10 5 -9 5 -10 6
3 -7 3 -3 2 -8 4
3 -6 -1 -6 -2 -5 -1

output:

9.404761904761904761987368
6

result:

ok 2 numbers

Test #2:

score: 0
Accepted
time: 1ms
memory: 4096kb

input:

3
1 -4 4
3 -2 6 0 5 2 6
3 -3 1 3 1 0 4
3 -2 2
3 -2 4 2 4 0 6
3 -2 2 -1 2 -2 3
3 1 2 2 2 2 3
3 -2 -1 0 -3 2 -1
1 1 2
3 -8 0 -7 0 -8 1
3 -5 0 -4 -1 -4 0

output:

-1
0
1

result:

ok 3 numbers

Test #3:

score: 0
Accepted
time: 1ms
memory: 4096kb

input:

1
1 -744567334 955216804
5 -781518205 -852078097 -781516900 -852078384 -781516392 -852076569 -781518329 -852076047 -781519925 -852077600
5 -393011614 -131855702 -393010699 -131856607 -393008846 -131856475 -393009388 -131854587 -393010201 -131854694

output:

1699779738.691979192313738

result:

ok found '1699779738.691979170', expected '1699779738.691979170', error '0.000000000'

Test #4:

score: 0
Accepted
time: 183ms
memory: 3968kb

input:

16666
2 -732787031 -732787030
3 -798263477 735869144 -583647039 529057159 -583647039 529057160
3 -777230180 499482549 -777230181 499482549 -777230180 499482548
3 -661853868 251627327 -661853868 251627326 -661853867 251627327
2 463140451 463140452
3 232604219 637008523 797038205 345997813 797038205 3...

output:

-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
...

result:

ok 16666 numbers

Test #5:

score: 0
Accepted
time: 106ms
memory: 3968kb

input:

16667
2 -9 7
3 -8 4 -6 1 -4 2
3 6 13 2 12 3 10
3 -1 7 0 10 -3 4
2 -9 5
3 -8 10 -5 8 -4 10
3 10 -8 9 -11 12 -8
3 -10 -5 -8 -4 -7 -1
2 -6 5
3 -8 6 -7 6 -5 7
3 -2 -3 1 -4 -4 -2
3 1 10 0 10 -1 8
2 -9 9
3 -5 -11 -2 -11 -5 -8
3 6 -5 5 -2 4 -5
3 11 6 9 3 11 3
2 -6 5
3 -7 6 -8 7 -9 4
3 9 2 12 -3 11 0
3 -6 3...

output:

16
14
11
15.55555555555555555594105
-1
12
14
17
11
16
11
15
15
10
18
16
14
17
12
16
10
14
3.666666666666666666738947
16
14
17
11
19
13
14
11.80000000000000000017347
18
18
12
11.14285714285714285701895
12
15
9.5
19
20
13
13
14
15
15
14
15
13
2
16
14
14
17
15.39999999999999999965306
2
18
10
17
13.3999...

result:

ok 16667 numbers

Test #6:

score: 0
Accepted
time: 108ms
memory: 4096kb

input:

16667
2 -6 10
3 6 -8 8 -10 9 -7
3 -5 13 -6 10 -6 8
3 8 10 7 7 10 7
2 -8 7
3 2 -10 0 -12 3 -11
3 -6 -7 -3 -5 -4 -4
3 10 -3 8 -3 8 -6
2 -7 6
3 9 1 9 4 6 1
3 7 -6 4 -8 6 -8
3 -3 -12 -4 -10 -5 -14
2 -10 10
3 11 -4 9 -1 9 -3
3 -6 -7 -6 -8 -5 -5
3 -10 -7 -7 -10 -6 -10
2 -9 8
3 3 2 3 1 6 5
3 4 -2 0 -3 1 -3...

output:

16
12.14285714285714285701895
13
20
17
13
15
16
19
11
15
20
15
-1
14
19
17
13
13
1
11
18
11
19
17
4
15
14
14
20
18
-1
10
17
4
12
15
2
19
13
9
10
5.5
17
15
5.222222222222222222029475
5.666666666666666666955787
18
13
18
10.7142857142857142859621
12.5
11
16
15
14
16
15.57142857142857142807579
14
13
17
...

result:

ok 16667 numbers

Test #7:

score: 0
Accepted
time: 112ms
memory: 4096kb

input:

16667
2 -20 15
3 17 -17 22 -14 14 -16
3 -5 -12 -3 -8 -8 -12
3 11 8 15 10 8 8
2 -10 12
3 -14 -13 -19 -9 -11 -17
3 14 13 10 12 14 9
3 -5 -20 -7 -17 -7 -20
2 -11 10
3 0 -24 -1 -20 -5 -19
3 -12 -2 -15 -5 -12 -5
3 10 -21 14 -24 14 -19
2 -15 20
3 -3 -16 -4 -10 -6 -15
3 8 17 7 12 10 17
3 8 -7 10 -5 11 -3
2...

output:

35
22
21
29.23076923076923076816325
31
37
17.25
38
37
31
30
33
27
30
30
31
16.42857142857142857192421
24.875
32
34.25
33
5.400000000000000000086736
25
14.39999999999999999965306
36
38
27
36
31
33
32
11.33333333333333333304421
24
18
28
34
28.8842105263157894745607
30
35
22
26
28.875
17.5
24
28
35
31
...

result:

ok 16667 numbers

Test #8:

score: 0
Accepted
time: 111ms
memory: 3968kb

input:

16667
2 -19 19
3 18 -12 22 -15 20 -12
3 24 0 20 2 20 -3
3 15 25 18 20 19 22
2 -18 20
3 10 6 11 11 7 8
3 26 -21 20 -12 21 -17
3 -4 -13 -11 -19 -6 -18
2 -13 14
3 19 -4 20 0 17 -7
3 1 -8 6 -12 3 -7
3 12 -7 5 -2 10 -6
2 -18 12
3 14 -5 15 -6 17 -4
3 18 -20 15 -19 20 -22
3 14 -8 18 -3 12 -10
2 -14 15
3 17...

output:

38
38
13.80000000000000000017347
30
29
25
27
27
29
28
27
34
35
20
20
25
25
38
25
25.5
26
27
39
28
21
36
16.39999999999999999965306
36
22
23
3.666666666666666666088426
23
29
36
34
29
22.5
32
31
23
23
22.20000000000000000069389
30
34
31
34
17.2857142857142857140379
37
32
26
28
3.5555555555555555550736...

result:

ok 16667 numbers

Test #9:

score: 0
Accepted
time: 160ms
memory: 4096kb

input:

8334
5 -17 14
5 -9 13 -12 15 -15 10 -15 9 -13 9
5 24 4 22 9 17 13 20 8 23 4
4 -11 4 -12 6 -17 9 -14 6
5 -7 23 -10 19 -10 17 -1 23 -3 28
4 23 -16 20 -11 15 -7 11 -11
5 15 -9 14 -9 15 -12 19 -14 20 -10
5 -11 10
5 -4 8 -1 10 -13 16 -14 15 -9 11
5 9 2 12 5 14 10 2 4 4 1
5 20 -12 23 -15 29 -10 27 -9 22 -...

output:

20
15
34
21
25
21
21
35
6.333333333333333333044213
32
28
-1
25
30
38
35
8.916666666666666666088426
17.53333333333333333287074
23.84615384615384615397959
34
35
1
6.090909090909090909012058
31
23.25
22.92857142857142857192421
18.79999999999999999930611
38
31
18.7142857142857142859621
31
17.57142857142...

result:

ok 8334 numbers

Test #10:

score: 0
Accepted
time: 158ms
memory: 4096kb

input:

8334
5 -10 19
5 28 13 20 10 24 8 28 8 29 13
5 -5 24 -5 20 -1 19 4 22 -1 24
5 -15 11 -10 8 -9 8 -12 13 -14 16
5 -4 16 -5 11 -1 16 -1 18 -2 21
3 12 21 13 13 17 18
4 -19 7 -15 10 -19 14 -20 12
5 -19 10
5 17 10 14 10 11 8 10 6 11 4
3 -5 -2 -10 -7 -5 -12
4 18 -4 20 -1 20 2 15 -3
4 -16 -4 -20 -5 -16 -9 -1...

output:

29
29
27
35
35
27
33
33.40000000000000000138778
8.5
34
29
29
29
12
23
3.5
30
13.7142857142857142859621
30
23.42857142857142857192421
5.5
35
30.1875
20.68571428571428571369095
31
-1
26
29
-1
22
7
2
18.1111111111111111118821
10.2857142857142857140379
9
35
27
35
29
8.666666666666666666955787
3.66315789...

result:

ok 8334 numbers

Test #11:

score: 0
Accepted
time: 160ms
memory: 4096kb

input:

8334
5 -24 23
5 -2 -9 -8 -9 -5 -13 0 -14 1 -10
3 -15 -8 -10 -4 -16 -7
5 0 -45 1 -45 5 -41 4 -40 -2 -43
3 8 32 9 27 12 30
5 33 1 36 -2 41 1 43 4 32 6
5 5 -35 7 -34 5 -30 1 -30 -2 -33
5 -38 33
5 44 29 39 34 35 35 36 34 41 30
5 29 25 32 20 36 18 37 22 31 27
4 29 15 33 12 38 12 33 17
5 -33 -29 -33 -30 -...

output:

34.59999999999999999861222
-1
63
25
47.75
52.82352941176470588480196
49
62
50.5517241379310344820408
42
39
63
38.81818181818181818371061
37.73684210526315789546725
58
2.333333333333333333911574
51.63636363636363636395177
52
28.14285714285714285788631
60
35.45833333333333333217685
54
49
38.2307692307...

result:

ok 8334 numbers

Test #12:

score: 0
Accepted
time: 163ms
memory: 4096kb

input:

8334
5 -22 38
5 10 -32 12 -30 9 -25 6 -22 6 -27
4 -38 27 -38 24 -37 24 -35 29
4 42 14 42 17 41 18 39 11
3 4 13 -3 15 -1 10
5 -36 5 -27 13 -30 15 -34 13 -36 10
4 -17 -9 -16 -4 -21 -3 -19 -7
5 -28 20
5 41 -2 33 -9 35 -9 37 -8 38 -7
5 5 -15 4 -16 4 -19 5 -23 9 -23
3 -7 -39 -6 -40 -3 -37
3 34 3 37 4 30 ...

output:

57.71428571428571428769683
48
55
59
52.6666666666666666643537
54.3125
65
40.04048582995951417046188
5.14285714285714285788631
32.94117647058823529493399
61
41
58.82608695652173912832295
57
9.1875
66
68.64285714285714285615159
52.09999999999999999861222
67
43
53
59
65
60
-1
40
37.55555555555555555594...

result:

ok 8334 numbers

Test #13:

score: 0
Accepted
time: 294ms
memory: 3968kb

input:

8334
5 -27 34
10 -34 40 -35 39 -39 31 -40 27 -35 25 -30 26 -28 30 -27 33 -27 37 -31 39
9 19 20 21 24 19 29 17 29 16 28 7 16 9 12 13 11 16 15
6 1 -20 7 -28 11 -29 12 -26 10 -22 6 -17
10 40 -48 42 -45 43 -40 39 -36 35 -35 30 -37 28 -40 28 -45 30 -48 35 -50
7 44 -3 49 0 51 2 50 7 48 10 43 5 39 0
8 20 -...

output:

53.27999999999999999888978
59
71
59
11
47
4.599999999999999998612221
41.73333333333333333356463
71
17.73076923076923076816325
46.35294117647058823386552
70
43.93939393939393939225724
-1
44
43
61.28571428571428571230317
49
36.32142857142857142807579
63
34.33333333333333333217685
60
44.095238095238095...

result:

ok 8334 numbers

Test #14:

score: 0
Accepted
time: 294ms
memory: 3968kb

input:

8334
5 -20 29
10 32 17 27 20 25 20 20 16 26 6 31 5 32 5 36 6 37 9 36 14
7 -28 29 -28 33 -32 32 -37 29 -40 27 -37 26 -32 25
7 39 23 36 26 33 28 31 29 28 27 30 22 32 18
8 1 13 5 13 6 17 4 22 0 26 -4 24 -5 19 -3 15
8 -26 28 -23 23 -19 25 -15 29 -13 34 -23 36 -27 36 -27 33
8 4 39 2 38 -2 33 -2 32 0 27 3...

output:

49
51
55
-1
59
23.26666666666666666643537
40.53846153846153846367351
34.13513513513513513569775
28.39999999999999999965306
73
54.05263157894736842160044
59
18.16666666666666666608843
66
-1
-1
48
50
13.09090909090909090987942
60
55
63
42.75
50.64285714285714285615159
55
25.9090909090909090918553
28.3...

result:

ok 8334 numbers

Test #15:

score: 0
Accepted
time: 409ms
memory: 4096kb

input:

8334
5 -3126 3527
40 2524 -3205 2555 -3204 2565 -3202 2571 -3200 2573 -3199 2582 -3194 2590 -3189 2593 -3187 2597 -3182 2603 -3174 2608 -3164 2610 -3159 2612 -3149 2611 -3139 2608 -3134 2606 -3132 2598 -3125 2588 -3120 2583 -3118 2575 -3115 2565 -3112 2555 -3110 2553 -3110 2544 -3111 2538 -3112 2528...

output:

6508.695260477869173776355
6121
5228.14605087984021247749
7545
6439.301684904757895999694
5552
7258
4340
7161
6347
6490.569421429937990275505
7132.550454048035018406182
5888.756053076135560164772
5827
4107
5813
6743
5977
6626
5587.25521134916039400764
6704.412641706233566551987
5040.2759891723780452...

result:

ok 8334 numbers

Test #16:

score: 0
Accepted
time: 412ms
memory: 3968kb

input:

8334
5 -2274 2353
40 2604 1999 2602 1992 2601 1985 2601 1984 2603 1974 2606 1965 2610 1955 2613 1948 2623 1940 2633 1938 2636 1939 2644 1944 2651 1949 2660 1956 2713 2008 2718 2015 2721 2021 2720 2031 2719 2040 2718 2048 2717 2051 2713 2060 2708 2070 2698 2078 2692 2080 2685 2082 2676 2083 2672 2082...

output:

4298.549625660067996069102
5799
4987.365051309711503790822
7308
5589.703760348221036835525
4652
6082.141746146348857848807
6086
3355.766144503350745909032
6459
6291
4838
4464.180612025333167558472
6093
6359
5211.003728784234597881664
4869.940969296873025662364
6031
7458
4466.892523364485981574035
56...

result:

ok 8334 numbers

Test #17:

score: 0
Accepted
time: 836ms
memory: 4224kb

input:

2274
5 -29040 32893
40 21293 3672 21285 3680 21278 3685 21271 3688 21266 3690 21258 3693 21255 3694 21254 3694 21245 3693 21239 3692 21223 3687 21218 3684 21214 3680 21208 3673 21203 3667 21198 3659 21195 3650 21193 3643 21191 3633 21194 3624 21198 3616 21203 3609 21211 3600 21220 3590 21221 3589 21...

output:

61933
35500.5
49406
67961.06673024960765872038
54610
63846
54004
48450.54339922606454038601
48956.33275865308729990488
60754
62140.87790921051610837367
68347.65153181557510464472
68003.03985160648530694516
57584
56121
72509
58579
48528
51409.77736672146331287081
56916
50965
63455
47426
53939
62687
4...

result:

ok 2274 numbers

Test #18:

score: 0
Accepted
time: 838ms
memory: 4224kb

input:

2271
5 -21608 38109
40 3288 29821 3282 29828 3277 29833 3268 29840 3258 29846 3256 29847 3250 29849 3240 29852 3233 29854 3228 29855 3220 29856 3218 29856 3212 29855 3210 29854 3205 29851 3197 29846 3189 29840 3179 29831 3176 29827 3171 29820 3165 29811 3163 29807 3160 29797 3167 29789 3172 29784 31...

output:

59717
62108
57257
66813.389315562535180959
65446
59441.15996084618944905742
55000
70062.36764271788123892293
61092.72227050713498641699
62176
58821
55055.67260985286614172196
52351
63396.88025841990810249627
51497
59209.96946518843044060532
68809.99886890207493195248
43824
69632
54865
57145
74565
59...

result:

ok 2271 numbers

Test #19:

score: 0
Accepted
time: 1022ms
memory: 4224kb

input:

1997
5 -685963307 853750511
100 372319561 823923262 372319594 823923310 372319621 823923350 372319653 823923400 372319681 823923445 372319710 823923492 372319721 823923511 372319739 823923548 372319750 823923572 372319764 823923603 372319780 823923639 372319785 823923651 372319795 823923692 37231980...

output:

1539712423.494848530157469
1259604092
1674868892
1100380125
1314807604
1476460075
1657770700
1681539925
1479119212
1631814313.223218382685445
1480527084
1718090694
1110684254
1648989975
1557856171
1841742140
1510489726
1928000884
1310353144
1145118694.755190038122237
1347709771
1588362127.9654922827...

result:

ok 1997 numbers

Test #20:

score: 0
Accepted
time: 1022ms
memory: 4096kb

input:

1998
5 -923518671 909017531
100 921654169 61734551 921654198 61734600 921654221 61734644 921654467 61735150 921654480 61735178 921654498 61735219 921654513 61735254 921654521 61735279 921654530 61735323 921654538 61735365 921654541 61735403 921654531 61735447 921654520 61735489 921654511 61735514 92...

output:

1832536202
1443062393.553619663813151
1680030554
1744446320.930086122010835
1205113181
1326796808
1213723402.194488483481109
1578305206.621328872861341
1334732988.958808328374289
1129359860.218818572815508
1542969200
1183125071.746443211100996
1404794757
1645873261
1131222178
1517285172
1856756798
1...

result:

ok 1998 numbers

Test #21:

score: 0
Accepted
time: 250ms
memory: 4096kb

input:

8334
5 -744567334 955216804
5 -781518205 -852078097 -781516900 -852078384 -781516392 -852076569 -781518329 -852076047 -781519925 -852077600
3 871916993 -588891734 871918253 -588892444 871918745 -588891234
5 -393011614 -131855702 -393010699 -131856607 -393008846 -131856475 -393009388 -131854587 -3930...

output:

1699779738.691979192313738
1527796251.090272669214755
1655793192.926833341945894
1672892305
1368134291
1463897904
1363175149
1296404984
1424194359
1029663073
1778254477
1503717633
1668133548
1493882251
1440932798.132074052235112
1487230105
1614511695.316303882282227
1421372056
1554693574.43057720665...

result:

ok 8334 numbers

Test #22:

score: 0
Accepted
time: 251ms
memory: 3968kb

input:

8334
5 -829825735 601784461
5 714610651 -975306485 714610404 -975306399 714609317 -975307983 714610491 -975308230 714610739 -975307741
5 -478043159 166470433 -478042674 166466411 -478041707 166468042 -478041795 166469844 -478042741 166471670
5 -574496064 117824476 -574497244 117826229 -574498481 117...

output:

1431606742.600444138166495
1730324827
1908650236.118417557328939
1890778564
1340666568
1319811364
1421853075
1490477103
1873755437
1570402518
1395074328
1612895854
1428358763
1323150903
1489866106
1541128379.772987372940406
1208364335
1511218105
1512984558
1361747390
1064194156.964996762864757
12694...

result:

ok 8334 numbers

Test #23:

score: 0
Accepted
time: 463ms
memory: 3968kb

input:

8334
5 -913048220 656325022
10 -166143242 -673183677 -166142264 -673184186 -166140797 -673184088 -166139127 -673183351 -166137499 -673182562 -166137324 -673182139 -166138589 -673181699 -166140193 -673181144 -166141964 -673181446 -166142469 -673181967
6 -945075435 650359787 -945076678 650360341 -9450...

output:

1569349415.914345892262645
1880676443
1316771742
1107991785
1549997697.444173724157736
1824059958
1444570056
1418459383
1505112947
1326424768.43103340070229
1369086579
1304632569.014852368272841
1440938152
1283836484
1676918571.102657952578738
1511733245
1572735322
1649259026.001737006707117
1517769...

result:

ok 8334 numbers

Test #24:

score: 0
Accepted
time: 465ms
memory: 3968kb

input:

8334
5 -894419066 986206278
10 438340992 -480519836 438342647 -480520761 438343571 -480520315 438344403 -480519603 438345824 -480518172 438346510 -480516618 438345277 -480515164 438343852 -480515669 438342447 -480516557 438340542 -480518404
10 -240550387 -258562092 -240551334 -258563442 -240550967 -...

output:

1880625344
1466897680.337360215140507
1494132112.283291047438979
1408363298.695816568098962
1390133394
1485867441.421866823220626
1590839506
1556522174.344312858767807
1614474976
1231693774
1493791516
1294379747
1456791864
1840525191
1343042881.426223344053142
1226808236.317833892768249
1658890773.7...

result:

ok 8334 numbers

Test #25:

score: 0
Accepted
time: 1029ms
memory: 4096kb

input:

2004
5 -851485863 922356807
100 806952389 -620838027 806952796 -620839051 806952929 -620839348 806953823 -620841099 806955255 -620843002 806956607 -620844576 806958351 -620846452 806958738 -620846812 806960698 -620848575 806962485 -620850179 806964065 -620851590 806965685 -620852945 806966771 -62085...

output:

1773665579.396214645006694
1245647086
1698103416.989566450472921
1192937188
1495810673
1331670703.053293028846383
1550766126
1572739123
1403505529.750806877505966
1564997181
1537044013
1092166901
1380042249.443731406703591
1665880122
1468783645
1479396541
1650669917
1654489929.983050543698482
182800...

result:

ok 2004 numbers

Test #26:

score: 0
Accepted
time: 1033ms
memory: 4096kb

input:

2001
5 -807916374 951640620
100 471800611 -609005450 471800882 -609005598 471802784 -609006412 471803897 -609006871 471804858 -609007255 471806094 -609007726 471807518 -609008221 471808084 -609008358 471830663 -609011338 471831366 -609011271 471832821 -609011131 471834532 -609010816 471835066 -60901...

output:

1759556994
1438355564
1162987446
1473770184
1660711599.304879248840734
1258059674
1509519860
1502232261.351548268459737
1622595242
1116409602
1497870504
1707338453
1606780390
1276518919.243549070321023
1353688653
1375742072.247927647200413
1172305883
1247991230.650028506992385
1471026036.81045036728...

result:

ok 2001 numbers

Test #27:

score: 0
Accepted
time: 453ms
memory: 3968kb

input:

10000
4 -876359283 597412519
84 -787103890 -543670676 -787103889 -543670617 -787103891 -543670566 -787103894 -543670542 -787103904 -543670486 -787103936 -543670413 -787103965 -543670352 -787104009 -543670286 -787104058 -543670216 -787104095 -543670169 -787104166 -543670087 -787104201 -543670047 -787...

output:

1473771802
1184445109
1273369968
1842104023.149110004073009
1401842961.365504766814411
1220676735
1584003979
1936415212.603602312272415
1439576635
1536198292
1744272262.969543530372903
1361024307
1572622937
1584471758.761927884304896
1862674505
1442207569.565795016009361
1373627850.679396792547777
1...

result:

ok 10000 numbers

Test #28:

score: 0
Accepted
time: 449ms
memory: 4096kb

input:

10000
4 -514589336 681051743
84 260136457 -778772788 260136398 -778772766 260136148 -778772704 260136080 -778772696 260135984 -778772691 260135939 -778772690 260135861 -778772692 260135765 -778772698 260135685 -778772707 260135618 -778772723 260135537 -778772753 260135478 -778772779 260135382 -77877...

output:

1195641079
1569912356
1518856735
1342714391
1214213079
1283220624
1796134134.931510697351769
1801713431
1728469471
1970762015
1597570818.429018666618504
1543786958
1445478087.780667074723169
1300840664
1647296924
1517434584
1242991475.714350626105443
1437348569
1299658132
1257135941
1682186294
10446...

result:

ok 10000 numbers

Test #29:

score: 0
Accepted
time: 458ms
memory: 3968kb

input:

10000
4 -854654469 777152266
84 -384437137 684560566 -384431810 684557290 -384422840 684552374 -384419937 684550899 -384413227 684547586 -384405159 684543922 -384396194 684540151 -384388285 684537901 -384381318 684537075 -384371666 684537161 -384370437 684537184 -384360706 684539373 -384351311 68454...

output:

1631806735
1424123468
1389677992.918774294201285
1576800025
1598916583
1464498679
1442804058
1666175099
1255050820.570157381473109
1561177121.734743743902072
1064468001.845047503069509
1105635482
1775824748.076137364492752
1463695468
1456224489.19731858430896
1653616905.973591265035793
1551751818
14...

result:

ok 10000 numbers

Test #30:

score: 0
Accepted
time: 452ms
memory: 3968kb

input:

10000
4 -771015246 658891315
84 45385710 -738165668 45385885 -738161269 45383143 -738154169 45381155 -738149591 45376641 -738139660 45372989 -738132856 45368735 -738126806 45366451 -738123774 45362745 -738119336 45356788 -738112594 45349125 -738104101 45342610 -738097460 45340181 -738095044 45333803...

output:

1429897974.608923890977167
1599820440
1236214920
1209017337.677535888622515
1873859588
1497435375.642676783725619
1478507602
1482210060
1260810353.914800924248993
1951395191.179261310491711
1753080128.449704686179757
1585952534
1759261924
1515725206
1529067000.752642959821969
1460498993
1760974739.4...

result:

ok 10000 numbers

Test #31:

score: 0
Accepted
time: 457ms
memory: 3968kb

input:

10000
4 -674914723 624418103
84 468468889 -499756104 468162339 -498888072 467601497 -497899887 466878219 -497038435 466134518 -496365273 465159179 -495560087 464211972 -495044122 464079613 -494973564 452212861 -493825380 452065957 -493824296 451407015 -493875285 450463932 -494062942 449543371 -49428...

output:

1264072929.761670227628201
1254262766
1663984089
1010711694.654035213636234
1470813291
1650827665.882998784072697
1254261966
1831622248
1374140339
1281253922.24806401040405
1567809316
1399880736.470407432178035
1620275496.955035088118166
1536577911
1675234428.528053288348019
1582493310
1146903499
14...

result:

ok 10000 numbers

Test #32:

score: 0
Accepted
time: 458ms
memory: 3968kb

input:

10000
4 -793175674 721626772
84 159345272 608883920 159698008 608015757 160118829 607278757 160699965 606292987 161301597 605353770 161836414 604600518 162258566 604103305 163119033 603125136 163652511 602547566 164390150 601772176 164814728 601358247 165571440 600703011 166011409 600345459 16678223...

output:

1504659632.681522995233536
1455208210
1338582258.145939962705597
1165325420.677496582968161
1454903090
1213494640
1777063188
1517563822.731618181569502
1068984015
1565287784
1375082267
1360915571
1499217617.692631965968758
1200971318
1248299373
1316644519
1582606361
1299261745
1440168826.22289606858...

result:

ok 10000 numbers

Test #33:

score: 0
Accepted
time: 289ms
memory: 6240kb

input:

5
10000 -525096166 506746434
3000 528096060 105801840 528097856 105801473 528099429 105801157 528100970 105800858 528101306 105800793 528101727 105800712 528103238 105800425 528104747 105800149 528105868 105799944 528107064 105799731 528108575 105799463 528110431 105799134 528111385 105798965 528112...

output:

397560103.4816339959506877
343764949.5169260488764849
314995685.8040496389730833
470388562.8405219377018511
369514676.7580897980369627

result:

ok 5 numbers

Test #34:

score: 0
Accepted
time: 307ms
memory: 6184kb

input:

5
10000 -501317113 815908190
3000 693478209 681557167 693478416 681557435 693479605 681558977 693480659 681560347 693481636 681561619 693481947 681562025 693482896 681563268 693484271 681565098 693485322 681566509 693486379 681567938 693487204 681569054 693488476 681570775 693489313 681571908 693490...

output:

1239559910.44609640724957
62025115.00769637104531284
621348456.9660612920997664
278611566.9257934705528896
934652762.2096404507756233

result:

ok 5 numbers

Test #35:

score: 0
Accepted
time: 718ms
memory: 8332kb

input:

5
10000 -700327508 702989707
3000 -254692935 -831597680 -254694172 -831597571 -254696030 -831597409 -254697316 -831597299 -254699111 -831597155 -254700632 -831597034 -254702548 -831596882 -254703508 -831596808 -254705371 -831596670 -254706070 -831596619 -254707817 -831596493 -254708500 -831596446 -2...

output:

240317371.9617961121402914
417228210.0622807190520689
145169437.6341325242246967
154695358.7931913889187854
661574446.5657238326966763

result:

ok 5 numbers

Test #36:

score: 0
Accepted
time: 732ms
memory: 8340kb

input:

5
10000 -535756158 936247062
3000 166383130 232330358 166382163 232330545 166381842 232330607 166381505 232330671 166380376 232330885 166379421 232331055 166377849 232331322 166376034 232331630 166374935 232331812 166373259 232332089 166371346 232332404 166370470 232332548 166369905 232332639 166369...

output:

321848681.54154536940041
47132901.3201733424430131
1221805373.452837745659053
1344708697.960075947339647
7305558.394949239824200049

result:

ok 5 numbers

Test #37:

score: 0
Accepted
time: 1329ms
memory: 35840kb

input:

2
10000 -758768479 517152843
3000 -196475875 -622544724 -196474245 -622545180 -196474129 -622545212 -196472878 -622545555 -196470969 -622546070 -196470160 -622546279 -196468698 -622546651 -196468113 -622546798 -196466578 -622547183 -196465475 -622547454 -196464203 -622547765 -196462700 -622548130 -1...

output:

253995254.6316990674386034
1328238926

result:

ok 2 numbers

Test #38:

score: 0
Accepted
time: 1315ms
memory: 35812kb

input:

2
10000 -573977895 641919861
3000 347121719 404913819 347122089 404915132 347122631 404917094 347122901 404918076 347123072 404918705 347123279 404919476 347123792 404921397 347124043 404922339 347124204 404922955 347124654 404924689 347125025 404926127 347125471 404927873 347125713 404928830 347126...

output:

173821476.891148404989508
1528471752

result:

ok 2 numbers

Test #39:

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

input:

1
648 -899534410 747361962
3000 211927638 493123207 211929268 493123656 211930155 493123901 211930800 493124086 211932237 493124502 211933656 493124916 211935226 493125375 211937118 493125929 211939099 493126531 211940702 493127019 211941925 493127397 211943096 493127759 211944029 493128048 21194475...

output:

1309979658.946250796550885

result:

ok found '1309979658.946250916', expected '1309979658.946250916', error '0.000000000'

Test #40:

score: 0
Accepted
time: 1271ms
memory: 35456kb

input:

1
657 -611575720 891439134
3000 491719655 -542798612 491719658 -542799409 491719666 -542801221 491719679 -542802627 491719693 -542804004 491719721 -542805714 491719761 -542807477 491719782 -542808319 491719830 -542809996 491719886 -542811761 491719897 -542812096 491719958 -542813875 491719996 -54281...

output:

1432477725.356502107577398

result:

ok found '1432477725.356502056', expected '1432477725.356502056', error '0.000000000'

Test #41:

score: 0
Accepted
time: 558ms
memory: 20392kb

input:

5
10000 -856871457 916406527
100000 623227399 -926813077 623226044 -926814196 623225217 -926814879 623223907 -926815961 623223067 -926816655 623221482 -926817965 623220871 -926818470 623220092 -926819114 623218435 -926820484 623218013 -926820833 623216069 -926822441 623214200 -926823987 623212464 -9...

output:

-1
-1
-1
-1
-1

result:

ok 5 numbers

Test #42:

score: 0
Accepted
time: 562ms
memory: 20468kb

input:

5
10000 -699668634 624085557
100000 506101157 -445281877 506099344 -445280103 506097486 -445278285 506096559 -445277378 506096281 -445277106 506094668 -445275528 506094484 -445275348 506093473 -445274359 506092374 -445273284 506091779 -445272702 506090503 -445271454 506089547 -445270519 506088365 -4...

output:

-1
-1
220429319.2044120462378487
-1
353925892.9909762743627653

result:

ok 5 numbers

Test #43:

score: 0
Accepted
time: 989ms
memory: 22256kb

input:

5
10000 -622037374 817682512
100000 -625558743 -704636222 -625558729 -704635708 -625558689 -704634239 -625558645 -704632623 -625558596 -704630818 -625558559 -704629455 -625558512 -704627718 -625558462 -704625869 -625558419 -704624273 -625558408 -704623864 -625558394 -704623343 -625558347 -704621591 ...

output:

-1
-1
-1
-1
-1

result:

ok 5 numbers

Test #44:

score: 0
Accepted
time: 998ms
memory: 22112kb

input:

5
10000 -644173104 652456201
100000 541445295 171993628 541445566 171995010 541445715 171995770 541445953 171996985 541445972 171997082 541446355 171999041 541446730 172000960 541447072 172002712 541447310 172003932 541447682 172005839 541448025 172007598 541448409 172009568 541448554 172010312 5414...

output:

-1
-1
-1
-1
218592599.1123368536063936

result:

ok 5 numbers

Test #45:

score: 0
Accepted
time: 1334ms
memory: 45360kb

input:

1
9046 -641166309 543165538
100000 -951104070 580563380 -951104422 580563946 -951105279 580565324 -951106332 580567017 -951107420 580568766 -951108596 580570656 -951109784 580572565 -951110770 580574149 -951111357 580575092 -951111743 580575712 -951112233 580576499 -951112464 580576870 -951113492 58...

output:

-1

result:

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

Test #46:

score: 0
Accepted
time: 1348ms
memory: 45360kb

input:

1
9045 -740410642 652751190
100000 419533646 402821427 419534234 402821769 419536223 402822926 419538064 402823997 419540039 402825146 419541895 402826226 419543842 402827359 419545349 402828236 419546581 402828953 419548227 402829911 419548818 402830255 419550371 402831159 419551522 402831829 41955...

output:

-1

result:

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

Test #47:

score: 0
Accepted
time: 1267ms
memory: 52148kb

input:

1
18 -948940253 629185104
100000 -833855325 174303631 -833856017 174302309 -833856901 174300620 -833857808 174298887 -833858536 174297496 -833859435 174295778 -833860349 174294031 -833861196 174292412 -833861887 174291091 -833862420 174290072 -833863407 174288185 -833864012 174287028 -833864551 1742...

output:

1389928213.815016854088753

result:

ok found '1389928213.815016747', expected '1389928213.815016747', error '0.000000000'

Test #48:

score: 0
Accepted
time: 1258ms
memory: 51724kb

input:

1
20 -934151185 527681557
100000 29124091 329049242 29124404 329047347 29124592 329046209 29124842 329044697 29125093 329043179 29125387 329041401 29125495 329040748 29125759 329039152 29126077 329037230 29126401 329035272 29126545 329034402 29126703 329033448 29126783 329032965 29127027 329031492 2...

output:

1461832742

result:

ok found '1461832742.000000000', expected '1461832742.000000000', error '0.000000000'

Extra Test:

score: 0
Extra Test Passed