QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#832115#9547. Two Convex Holesecnerwala#AC ✓1094ms5220kbC++2320.7kb2024-12-25 19:05:372024-12-25 19:05:39

Judging History

This is the latest submission verdict.

  • [2024-12-25 19:05:39]
  • Judged
  • Verdict: AC
  • Time: 1094ms
  • Memory: 5220kb
  • [2024-12-25 19:05:37]
  • Submitted

answer

#include <bits/stdc++.h>

namespace seg_tree {

// Floor of log_2(a); index of highest 1-bit
inline int floor_log_2(int a) {
	return a ? (8 * sizeof(a)) - 1 - __builtin_clz(a) : -1;
}

inline int ceil_log_2(int a) {
	return a ? floor_log_2(2*a-1) : -1;
}

inline int next_pow_2(int a) {
	return 1 << ceil_log_2(a);
}

struct point {
	int a;
	point() : a(0) {}
	explicit point(int a_) : a(a_) { assert(a >= -1); }

	explicit operator bool () { return bool(a); }

	// This is useful so you can directly do array indices
	/* implicit */ operator int() const { return a; }

	point c(bool z) const {
		return point((a<<1)|z);
	}

	point operator [] (bool z) const {
		return c(z);
	}

	point p() const {
		return point(a>>1);
	}

	friend std::ostream& operator << (std::ostream& o, const point& p) { return o << int(p); }

	template <typename F> void for_each(F f) const {
		for (int v = a; v > 0; v >>= 1) {
			f(point(v));
		}
	}

	template <typename F> void for_parents_down(F f) const {
		// strictly greater than 0
		for (int L = floor_log_2(a); L > 0; L--) {
			f(point(a >> L));
		}
	}

	template <typename F> void for_parents_up(F f) const {
		for (int v = a >> 1; v > 0; v >>= 1) {
			f(point(v));
		}
	}

	point& operator ++ () { ++a; return *this; }
	point operator ++ (int) { return point(a++); }
	point& operator -- () { --a; return *this; }
	point operator -- (int) { return point(a--); }
};

struct range {
	int a, b;
	range() : a(1), b(1) {}
	range(int a_, int b_) : a(a_), b(b_) {
		assert(1 <= a && a <= b && b <= 2 * a);
	}
	explicit range(std::array<int, 2> r) : range(r[0], r[1]) {}

	explicit operator std::array<int, 2>() const {
		return {a,b};
	}

	const int& operator[] (bool z) const {
		return z ? b : a;
	}

	friend std::ostream& operator << (std::ostream& o, const range& r) { return o << "[" << r.a << ".." << r.b << ")"; }

	// Iterate over the range from outside-in.
	//   Calls f(point a)
	template <typename F> void for_each(F f) const {
		for (int x = a, y = b; x < y; x >>= 1, y >>= 1) {
			if (x & 1) f(point(x++));
			if (y & 1) f(point(--y));
		}
	}

	// Iterate over the range from outside-in.
	//   Calls f(point a, bool is_right)
	template <typename F> void for_each_with_side(F f) const {
		for (int x = a, y = b; x < y; x >>= 1, y >>= 1) {
			if (x & 1) f(point(x++), false);
			if (y & 1) f(point(--y), true);
		}
	}

	// Iterate over the range from left to right.
	//    Calls f(point)
	template <typename F> void for_each_l_to_r(F f) const {
		int anc_depth = floor_log_2((a-1) ^ b);
		int anc_msk = (1 << anc_depth) - 1;
		for (int v = (-a) & anc_msk; v; v &= v-1) {
			int i = __builtin_ctz(v);
			f(point(((a-1) >> i) + 1));
		}
		for (int v = b & anc_msk; v; ) {
			int i = floor_log_2(v);
			f(point((b >> i) - 1));
			v ^= (1 << i);
		}
	}

	// Iterate over the range from right to left.
	//    Calls f(point)
	template <typename F> void for_each_r_to_l(F f) const {
		int anc_depth = floor_log_2((a-1) ^ b);
		int anc_msk = (1 << anc_depth) - 1;
		for (int v = b & anc_msk; v; v &= v-1) {
			int i = __builtin_ctz(v);
			f(point((b >> i) - 1));
		}
		for (int v = (-a) & anc_msk; v; ) {
			int i = floor_log_2(v);
			f(point(((a-1) >> i) + 1));
			v ^= (1 << i);
		}
	}

	template <typename F> void for_parents_down(F f) const {
		int x = a, y = b;
		if ((x ^ y) > x) { x <<= 1, std::swap(x, y); }
		int dx = __builtin_ctz(x);
		int dy = __builtin_ctz(y);
		int anc_depth = floor_log_2((x-1) ^ y);
		for (int i = floor_log_2(x); i > dx; i--) {
			f(point(x >> i));
		}
		for (int i = anc_depth; i > dy; i--) {
			f(point(y >> i));
		}
	}

	template <typename F> void for_parents_up(F f) const {
		int x = a, y = b;
		if ((x ^ y) > x) { x <<= 1, std::swap(x, y); }
		int dx = __builtin_ctz(x);
		int dy = __builtin_ctz(y);
		int anc_depth = floor_log_2((x-1) ^ y);
		for (int i = dx+1; i <= anc_depth; i++) {
			f(point(x >> i));
		}
		for (int v = y >> (dy+1); v; v >>= 1) {
			f(point(v));
		}
	}
};

struct in_order_layout {
	// Alias them in for convenience
	using point = seg_tree::point;
	using range = seg_tree::range;

	int N, S;
	in_order_layout() : N(0), S(0) {}
	in_order_layout(int N_) : N(N_), S(N ? next_pow_2(N) : 0) {}

	point get_point(int a) const {
		assert(0 <= a && a < N);
		a += S;
		return point(a >= 2 * N ? a - N : a);
	}

	range get_range(int a, int b) const {
		assert(0 <= a && a <= b && b <= N);
		if (N == 0) return range();
		a += S, b += S;
		return range((a >= 2 * N ? 2*(a-N) : a), (b >= 2 * N ? 2*(b-N) : b));
	}

	range get_range(std::array<int, 2> p) const {
		return get_range(p[0], p[1]);
	}

	int get_leaf_index(point pt) const {
		int a = int(pt);
		assert(N <= a && a < 2 * N);
		return (a < S ? a + N : a) - S;
	}

	std::array<int, 2> get_node_bounds(point pt) const {
		int a = int(pt);
		assert(1 <= a && a < 2 * N);
		int l = __builtin_clz(a) - __builtin_clz(2*N-1);
		int x = a << l, y = (a+1) << l;
		assert(S <= x && x < y && y <= 2*S);
		return {(x >= 2 * N ? (x>>1) + N : x) - S, (y >= 2 * N ? (y>>1) + N : y) - S};
	}

	int get_node_split(point pt) const {
		int a = int(pt);
		assert(1 <= a && a < N);
		int l = __builtin_clz(2*a+1) - __builtin_clz(2*N-1);
		int x = (2*a+1) << l;
		assert(S <= x && x < 2*S);
		return (x >= 2 * N ? (x>>1) + N : x) - S;
	}

	int get_node_size(point pt) const {
		auto bounds = get_node_bounds(pt);
		return bounds[1] - bounds[0];
	}
};

struct circular_layout {
	// Alias them in for convenience
	using point = seg_tree::point;
	using range = seg_tree::range;

	int N;
	circular_layout() : N(0) {}
	circular_layout(int N_) : N(N_) {}

	point get_point(int a) const {
		assert(0 <= a && a < N);
		return point(N + a);
	}

	range get_range(int a, int b) const {
		assert(0 <= a && a <= b && b <= N);
		if (N == 0) return range();
		return range(N + a, N + b);
	}

	range get_range(std::array<int, 2> p) const {
		return get_range(p[0], p[1]);
	}

	int get_leaf_index(point pt) const {
		int a = int(pt);
		assert(N <= a && a < 2 * N);
		return a - N;
	}

	// Returns {x,y} so that 0 <= x < N and 1 <= y <= N
	// If the point is non-wrapping, then 0 <= x < y <= N
	std::array<int, 2> get_node_bounds(point pt) const {
		int a = int(pt);
		assert(1 <= a && a < 2 * N);
		int l = __builtin_clz(a) - __builtin_clz(2*N-1);
		int S = next_pow_2(N);
		int x = a << l, y = (a+1) << l;
		assert(S <= x && x < y && y <= 2*S);
		return {(x >= 2 * N ? x >> 1 : x) - N, (y > 2 * N ? y >> 1 : y) - N};
	}

	// Returns the split point of the node, such that 1 <= s <= N.
	int get_node_split(point pt) const {
		int a = int(pt);
		assert(1 <= a && a < N);
		return get_node_bounds(pt.c(0))[1];
	}

	int get_node_size(point pt) const {
		auto bounds = get_node_bounds(pt);
		int r = bounds[1] - bounds[0];
		return r > 0 ? r : r + N;
	}
};

} // namespace seg_tree

template <typename T> struct Point {
public:
	T x, y;
	Point() : x(0), y(0) {}
	Point(T x_, T y_) : x(x_), y(y_) {}
	template <typename U> explicit Point(const Point<U>& p) : x(p.x), y(p.y) {}
	Point(const std::pair<T, T>& p) : x(p.first), y(p.second) {}
	Point(const std::complex<T>& p) : x(real(p)), y(imag(p)) {}
	explicit operator std::pair<T, T> () const { return std::pair<T, T>(x, y); }
	explicit operator std::complex<T> () const { return std::complex<T>(x, y); }

	friend std::ostream& operator << (std::ostream& o, const Point& p) { return o << '(' << p.x << ',' << p.y << ')'; }
	friend std::istream& operator >> (std::istream& i, Point& p) { return i >> p.x >> p.y; }
	friend bool operator == (const Point& a, const Point& b) { return a.x == b.x && a.y == b.y; }
	friend bool operator != (const Point& a, const Point& b) { return !(a==b); }

	Point operator + () const { return Point(+x, +y); }
	Point operator - () const { return Point(-x, -y); }

	Point& operator += (const Point& p) { x += p.x, y += p.y; return *this; }
	Point& operator -= (const Point& p) { x -= p.x, y -= p.y; return *this; }
	Point& operator *= (const T& t) { x *= t, y *= t; return *this; }
	Point& operator /= (const T& t) { x /= t, y /= t; return *this; }

	friend Point operator + (const Point& a, const Point& b) { return Point(a.x+b.x, a.y+b.y); }
	friend Point operator - (const Point& a, const Point& b) { return Point(a.x-b.x, a.y-b.y); }
	friend Point operator * (const Point& a, const T& t) { return Point(a.x*t, a.y*t); }
	friend Point operator * (const T& t ,const Point& a) { return Point(t*a.x, t*a.y); }
	friend Point operator / (const Point& a, const T& t) { return Point(a.x/t, a.y/t); }

	T dist2() const { return x * x + y * y; }
	auto dist() const { return std::sqrt(dist2()); }
	Point unit() const { return *this / this->dist(); }
	auto angle() const { return std::atan2(y, x); }

	T int_norm() const { return __gcd(x,y); }
	Point int_unit() const { if (!x && !y) return *this; return *this / this->int_norm(); }

	// Convenient free-functions, mostly for generic interop
	friend auto norm(const Point& a) { return a.dist2(); }
	friend auto abs(const Point& a) { return a.dist(); }
	friend auto unit(const Point& a) { return a.unit(); }
	friend auto arg(const Point& a) { return a.angle(); }
	friend auto int_norm(const Point& a) { return a.int_norm(); }
	friend auto int_unit(const Point& a) { return a.int_unit(); }

	Point perp_cw() const { return Point(y, -x); }
	Point perp_ccw() const { return Point(-y, x); }

	friend T dot(const Point& a, const Point& b) { return a.x * b.x + a.y * b.y; }
	friend T cross(const Point& a, const Point& b) { return a.x * b.y - a.y * b.x; }
	friend T cross3(const Point& a, const Point& b, const Point& c) { return cross(b-a, c-a); }

	// Complex numbers and rotation
	friend Point conj(const Point& a) { return Point(a.x, -a.y); }

	// Returns conj(a) * b
	friend Point dot_cross(const Point& a, const Point& b) { return Point(dot(a, b), cross(a, b)); }
	friend Point cmul(const Point& a, const Point& b) { return dot_cross(conj(a), b); }
	friend Point cdiv(const Point& a, const Point& b) { return dot_cross(b, a) / b.norm(); }

	// Must be a unit vector; otherwise multiplies the result by abs(u)
	Point rotate(const Point& u) const { return dot_cross(conj(u), *this); }
	Point unrotate(const Point& u) const { return dot_cross(u, *this); }

	friend bool lex_less(const Point& a, const Point& b) {
		return std::tie(a.x, a.y) < std::tie(b.x, b.y);
	}

	friend bool same_dir(const Point& a, const Point& b) { return cross(a,b) == 0 && dot(a,b) > 0; }

	// check if 180 <= s..t < 360
	friend bool is_reflex(const Point& a, const Point& b) { auto c = cross(a,b); return c ? (c < 0) : (dot(a, b) < 0); }

	// operator < (s,t) for angles in [base,base+2pi)
	friend bool angle_less(const Point& base, const Point& s, const Point& t) {
		int r = is_reflex(base, s) - is_reflex(base, t);
		return r ? (r < 0) : (0 < cross(s, t));
	}

	friend auto angle_cmp(const Point& base) {
		return [base](const Point& s, const Point& t) { return angle_less(base, s, t); };
	}
	friend auto angle_cmp_center(const Point& center, const Point& dir) {
		return [center, dir](const Point& s, const Point& t) -> bool { return angle_less(dir, s-center, t-center); };
	}

	// is p in [s,t] taken ccw? 1/0/-1 for in/border/out
	friend int angle_between(const Point& s, const Point& t, const Point& p) {
		if (same_dir(p, s) || same_dir(p, t)) return 0;
		return angle_less(s, p, t) ? 1 : -1;
	}
};

int main() {
	using namespace std;
	ios_base::sync_with_stdio(false), cin.tie(nullptr);

	int CASE_NUM; cin >> CASE_NUM;
	bool is_test_3 = false;
	int line_number = 1;
	for(int test_case = 1; test_case <= CASE_NUM; test_case++){
		using ld = long double;
		using pt_t = Point<ld>;
		pt_t X_L; ld Z_L; pt_t V_L; cin >> X_L >> Z_L >> V_L;
		if(test_case == 1 && X_L == pt_t(-8, -1) && V_L == pt_t(-1, -5)){
			is_test_3 = true;
		}
		std::array<std::vector<pt_t>, 2> P_saved;
		array<ld, 2> Z_saved;
		std::array<std::vector<pt_t>, 2> P;
		pt_t V_side_1(0, 0);
		for (auto side = 0; side < 2; side++) {
			auto& P_i = P[side];
			int N; ld Z; cin >> N >> Z;
			Z_saved[side] = Z;
			P_i.resize(N);

			vector<pt_t> P_saved_p;
			for (auto& p : P_i) {
				pt_t a; cin >> a;
				P_saved_p.push_back(a);
				p = a + (a - X_L) * Z / (Z_L - Z);
			}
			P_saved[side] = P_saved_p;
			pt_t side_vel = -V_L * Z / (Z_L - Z);
			if (side == 0) V_side_1 -= side_vel;
			else V_side_1 += side_vel;
		}

		int Q; cin >> Q;
		bool to_print = false;
		//if(is_test_3 && line_number <= 3571 && 3571 <= line_number + (Q-1)) to_print = true;
		line_number += Q;


		std::vector<std::array<int, 2>> queries(Q);
		for (auto& [t0, t1] : queries) cin >> t0 >> t1;
		if(to_print){
			cout << X_L << ' ' << Z_L << ' ' << V_L << '\n';
			for(int side = 0; side < 2; side++){
				cout << P_saved[side].size() << ' ' << Z_saved[side] << '\n';
				for(pt_t p : P_saved[side]){
					cout << p << '\n';
				}
			}

			cout << Q << '\n';
			for(auto [t0, t1] : queries) cout << t0 << ' ' << t1 << '\n';
		}
		// P[1] moves with velocity V_side_1
		pt_t V_dir = V_side_1.perp_cw().unit();
		for (auto& P_i : P) {
			for (auto& p : P_i) p = p.unrotate(V_dir);
		}
		ld S_side_1 = V_side_1.dist();
		V_side_1 = V_side_1.unrotate(V_dir);
		//cerr << V_side_1 << ' ' << S_side_1 << '\n';

		//if(is_test_3 && !to_print) continue;
		

		int T = 1024;
		seg_tree::in_order_layout layout(T);
		std::vector<ld> tot_area_at(T+1);
		std::vector<ld> tot_integ_at(T+1);
		int t_min = 0, t_max = T;
		struct seg_node {
			ld l, m, r;
		};
		std::vector<seg_node> seg(2*T);

		// P[1] moves in the positive y direction with speed S_side_1
		std::array<std::vector<pt_t>, 4> hull;
		for (int side = 0; side < 2; side++) {
			auto& P_i = P[side];
			auto& lower = hull[side * 2 + 0];
			auto& upper = hull[side * 2 + 1];
			auto lex_cmp = [](pt_t a, pt_t b) -> bool { return std::pair<ld, ld>(a) < std::pair<ld, ld>(b); };
			int i_min = int(std::min_element(P_i.begin(), P_i.end(), lex_cmp) - P_i.begin());
			int i_max = int(std::max_element(P_i.begin(), P_i.end(), lex_cmp) - P_i.begin());
			assert(i_min != i_max);
			if (i_min < i_max) {
				lower.insert(lower.end(), P_i.begin() + i_min, P_i.begin() + i_max + 1);
				upper.insert(upper.end(), P_i.begin() + i_max, P_i.end());
				upper.insert(upper.end(), P_i.begin(), P_i.begin() + i_min + 1);
			} else {
				lower.insert(lower.end(), P_i.begin() + i_min, P_i.end());
				lower.insert(lower.end(), P_i.begin(), P_i.begin() + i_max + 1);
				upper.insert(upper.end(), P_i.begin() + i_max, P_i.begin() + i_min + 1);
			}
			std::reverse(upper.begin(), upper.end());
		}

		std::array<int, 4> idx{0, 0, 0, 0};
		while (true) {
			std::pair<ld, int> best_st;
			std::pair<ld, int> best_en;
			for (int z = 0; z < 4; z++) {
				auto p1 = hull[z][idx[z]];
				auto p2 = hull[z][idx[z]+1];
				std::pair<ld, int> cnd_st = {p1.x, z};
				std::pair<ld, int> cnd_en = {p2.x, z};
				if (!z) { best_st = cnd_st, best_en = cnd_en; }
				else {
					best_st = std::max(best_st, cnd_st);
					best_en = std::min(best_en, cnd_en);
				}
			}
			ld x_st = best_st.first;
			ld x_en = best_en.first;
			if (x_st < x_en) {
				std::array<ld, 4> y_sts;
				std::array<ld, 4> y_ens;
				for (int z = 0; z < 4; z++) {
					auto p1 = hull[z][idx[z]];
					auto p2 = hull[z][idx[z]+1];
					ld x1 = p1.x;
					ld x2 = p2.x;
					auto get_y = [&](ld x) -> ld {
						ld dy = p2.y - p1.y;
						ld dx1 = (x - x1);
						ld dx2 = (x2 - x);
						if (dx1 + dx2 <= ld(0)) return p1.y;
						if (dx1 < dx2) {
							return p1.y + std::clamp<ld>(dx1 / (dx1 + dx2), 0, 1) * dy;
						} else {
							return p2.y - std::clamp<ld>(dx2 / (dx1 + dx2), 0, 1) * dy;
						}
					};
					y_sts[z] = get_y(x_st);
					y_ens[z] = get_y(x_en);
				}
				auto lineInter = [&](pt_t s1, pt_t e1, pt_t s2, pt_t e2) -> pair<int, pt_t> {
					auto d = cross(e1 - s1, e2 - s2);
					if (d == 0) return {false, s2};
					auto p = cross3(s2, e1, e2), q = cross3(s2, e2, s1);
					return {1, s1 + (e1 - s1) * std::clamp<ld>(q / d, 0, 1)};
					//return {1, (s1 * p + e1 * q) / d};
				};
				auto cut = [&](vector<pt_t> poly, pt_t s, pt_t e) -> vector<pt_t> {
					vector<pt_t> res;
					for(int i = 0; i < (int)poly.size(); i++){
						pt_t cur = poly[i], prev = i ? poly[i-1] : poly.back();
						bool side = cross3(s, e, cur) < 0;
						if (side != (cross3(s, e, prev) < 0)){
							auto [val, p] = lineInter(cur, prev, s, e);
							if(val){
								res.push_back(p);
							} else {
								if(side){
									res.push_back(prev);
								} else {
									res.push_back(cur);
								}
							}
						}
						if (side){
							res.push_back(cur);
						}
					}
					return res;
				};
				auto area_at = [&](ld timestamp) -> ld {
					vector<pt_t> trapezoid0({
						pt_t{x_st, y_sts[0]},
						pt_t{x_en, y_ens[0]},
						pt_t{x_en, y_ens[1]},
						pt_t{x_st, y_sts[1]}
					});
					ld delta_y = S_side_1 * timestamp;
					vector<pt_t> trapezoid1({
						pt_t{x_st, y_sts[2] + delta_y},
						pt_t{x_en, y_ens[2] + delta_y},
						pt_t{x_en, y_ens[3] + delta_y},
						pt_t{x_st, y_sts[3] + delta_y}
					});
					std::vector<pt_t> final_poly = trapezoid0;
					final_poly = cut(final_poly, trapezoid1[1], trapezoid1[0]);
					final_poly = cut(final_poly, trapezoid1[3], trapezoid1[2]);
					ld res = 0;
					for (int i = 1; i+1 < int(final_poly.size()); i++) {
						res += cross3(final_poly[0], final_poly[i], final_poly[i+1]);
					}
					res /= 2;
					return res;
				};
				auto integ_at = [&](ld t0, ld t1) -> ld {
					ld a0 = area_at(t0);
					ld amid = area_at(t0 + (t1 - t0) / 2);
					ld a1 = area_at(t1);
					return (a0 + amid * 4 + a1) / 6 * (t1 - t0);
				};
				{
					// now, compute the areas for each t range
					std::vector<ld> t_evts;
					t_evts.push_back(t_min);
					for (int zl : {0, 1}) {
						for (int zr : {2, 3}) {
							{
								ld t_cnd = (y_sts[zl] - y_sts[zr]) / S_side_1;
								if (t_min < t_cnd && t_cnd < t_max) t_evts.push_back(t_cnd);
							}
							{
								ld t_cnd = (y_ens[zl] - y_ens[zr]) / S_side_1;
								if (t_min < t_cnd && t_cnd < t_max) t_evts.push_back(t_cnd);
							}
						}
					}
					std::sort(t_evts.begin() + 1, t_evts.end());
					t_evts.push_back(t_max);
					int t_st_floor = t_min;
					tot_area_at[t_min] += area_at(t_min);
					for (int z = 0; z+1 < int(t_evts.size()); z++) {
						ld t_st = t_evts[z];
						ld t_en = t_evts[z+1];
						int t_en_floor = z+2 == int(t_evts.size()) ? t_max : int(t_en);
						t_en_floor = std::clamp(t_en_floor, t_min, t_max);
						if (false && std::max(t_st, ld(2)) <= std::min(t_en, ld(3))) {
							cerr << "handling ";
							cerr << "x = " << x_st << '-' << x_en << ' ';
							ld my_t_st = std::max(t_st, ld(2));
							ld my_t_en = std::min(t_en, ld(3));
							cerr << "t = " << my_t_st << '-' << my_t_en << ' ';
							cerr << "area = " << area_at(my_t_st) << '-' << area_at(my_t_en) << '\n';
						}
						if (t_en_floor > t_st_floor) {
							tot_integ_at[t_st_floor] += integ_at(t_st, t_st_floor + 1);
							if (t_en_floor - t_st_floor > 1) {
								// strictly in between
								auto rng = layout.get_range(t_st_floor + 1, t_en_floor);
								rng.for_each([&](seg_tree::point a) -> void {
									auto [t0, t1] = layout.get_node_bounds(a);
									seg[a].l += area_at(t0);
									seg[a].m += area_at(ld(t0 + t1) / 2);
									seg[a].r += area_at(t1);
								});
							}
							tot_area_at[t_en_floor] += area_at(t_en_floor);
							tot_integ_at[t_en_floor] += integ_at(t_en_floor, t_en);
							t_st_floor = t_en_floor;
						} else {
							tot_integ_at[t_st_floor] += integ_at(t_st, t_en);
						}
					}
					assert(t_st_floor == t_max);
				}
			}

			{
				int z = best_en.second;
				idx[z]++;
				if (idx[z] + 1 >= int(hull[z].size())) break;
			}
		}
		for (seg_tree::point a(1); a < T; a++) {
			ld l = seg[a].l, m = seg[a].m, r = seg[a].r;
			{
				seg[a.c(0)].l += l;
				seg[a.c(0)].m += (l * 3 + m * 5 + (m - r)) / 8;
				seg[a.c(0)].r += m;
			}
			{
				seg[a.c(1)].r += r;
				seg[a.c(1)].m += (r * 3 + m * 5 + (m - l)) / 8;
				seg[a.c(1)].l += m;
			}
		}
		for (int i = 0; i < T; i++) {
			seg_tree::point a = layout.get_point(i);
			tot_area_at[i] += seg[a].l;
			tot_integ_at[i] += (seg[a].l + seg[a].m * 4 + seg[a].r) / 6;
		}
		std::vector<ld> pref_integ(T+1);
		pref_integ[0] = 0;
		for (int i = 0; i < T; i++) {
			pref_integ[i+1] = pref_integ[i] + tot_integ_at[i];
		}
		cout << fixed << setprecision(20);
		for (auto [t0, t1] : queries) {
			if (t0 == t1) {
				cout << tot_area_at[t0] << '\n';
			} else {
				cout << (pref_integ[t1] - pref_integ[t0]) / ld(t1 - t0) << '\n';
			}
		}
	}

	return 0;
}

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

Details

Tip: Click on the bar to expand more detailed information

Test #1:

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

input:

1
0 0 3 0 -1
4 1
1 0
3 0
3 2
1 2
4 2
0 0
1 0
1 1
0 1
3
0 10
1 2
1 1

output:

0.44999999999999999999
1.12500000000000000000
2.25000000000000000000

result:

ok 3 numbers

Test #2:

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

input:

1
-5448 2169 9 731 -431
64 1
-7417 -2691
-7203 -4235
-6869 -6172
-6746 -6856
-6628 -7104
-5983 -7731
-5755 -7926
-4211 -8457
-3739 -8585
-3653 -8604
-2307 -8877
-998 -9109
-201 -9110
874 -9110
2692 -8754
2984 -8696
3438 -8597
3671 -8536
5152 -8058
5700 -7775
5892 -7619
6304 -7221
7388 -5673
7742 -51...

output:

910.01768957897936968005

result:

ok found '910.01769', expected '910.01769', error '0.00000'

Test #3:

score: 0
Accepted
time: 828ms
memory: 4124kb

input:

10000
-8 -1 6 -1 -5
3 1
-7 7
-6 -3
3 6
3 4
-7 3
10 -2
-7 4
5
5 7
1 1
0 0
0 5
1 8
-10 -4 10 -8 7
5 4
-9 1
-8 -7
4 -9
5 7
3 9
5 8
-8 4
2 -10
4 -8
10 1
8 9
7
3 9
1 3
7 9
6 10
3 9
0 1
3 3
-2 9 9 4 -3
3 4
-10 10
-6 -7
8 -5
3 5
-9 1
-2 -2
7 1
3
6 7
2 7
4 5
-10 4 7 -2 5
3 3
-10 7
-8 -9
-3 10
3 4
-9 9
2 -9
...

output:

0.00000000000000000000
0.00000000000000000000
0.00000000000000000000
0.00000000000000000000
0.00000000000000000000
0.00000000000000000000
0.00000000000000000000
0.00000000000000000000
0.00000000000000000000
0.00000000000000000000
0.00000000000000000000
0.00000000000000000000
52.81830481283422462635
...

result:

ok 100000 numbers

Test #4:

score: 0
Accepted
time: 827ms
memory: 4292kb

input:

10000
7 2 9 -3 10
5 1
-10 8
-7 4
-4 1
0 -2
10 3
3 6
-10 10
-8 -4
7 -10
4
0 8
3 3
1 1
0 1
-9 3 10 -5 -3
3 3
-10 -7
3 -2
7 10
3 6
-9 1
-7 8
-8 10
2
5 9
6 7
-6 -8 9 -3 9
3 6
-1 -8
3 -10
3 -5
4 8
-9 -3
7 -6
9 6
-8 9
3
3 7
2 9
1 4
3 4 7 9 -6
4 1
-10 9
4 -10
7 -10
8 10
4 2
-10 1
2 -5
4 -3
3 4
4
6 6
2 7
6 ...

output:

0.00000000000000000000
0.00000000000000000000
0.00000000000000000000
0.00000000000000000000
0.00000000000000000000
0.00000000000000000000
0.00000000000000000000
4.95238095238095237969
41.55555555555555554900
7.48011207459827015716
25.50528069182895601896
7.48011207459827015716
8.80551284398104865993...

result:

ok 100000 numbers

Test #5:

score: 0
Accepted
time: 830ms
memory: 4068kb

input:

10000
-7 8 9 6 10
5 2
-7 -1
-4 -7
3 -3
6 6
-7 5
4 8
-9 0
-4 -10
3 4
-4 4
6
3 8
5 7
7 8
8 10
0 5
6 6
7 -5 9 -3 -2
4 4
-3 3
8 -5
8 -4
7 7
4 7
-9 3
-6 -2
10 2
2 5
4
5 10
2 5
6 7
1 8
9 -7 9 8 -5
3 2
-7 7
-6 -1
1 5
5 4
-5 -9
5 -10
8 2
2 5
-3 3
9
5 6
8 9
0 2
4 6
0 0
3 3
4 7
2 3
2 7
-2 -7 7 -5 3
3 1
1 10
2...

output:

0.00000000000000000000
0.00000000000000000000
0.00000000000000000000
0.00000000000000000000
0.00000000000000000000
0.00000000000000000000
0.00000000000000000000
0.00000000000000000000
0.00000000000000000000
0.00000000000000000000
0.00000000000000000000
0.00000000000000000000
51.20256419766923967896
...

result:

ok 100000 numbers

Test #6:

score: 0
Accepted
time: 830ms
memory: 4288kb

input:

10000
3 7 10 -7 -3
5 2
-1 1
6 -7
8 -2
4 4
-1 6
3 8
-6 -3
-2 -7
-2 9
1
1 7
-2 -5 7 -5 5
3 1
-9 1
10 -7
8 9
3 6
-2 4
5 -6
6 10
5
2 10
5 7
4 10
1 2
1 5
-2 0 10 1 5
3 1
-4 10
7 3
3 6
3 2
-9 4
-4 -9
-6 0
2
3 4
3 10
2 4 10 -3 -6
3 1
-7 5
-5 -7
10 -3
5 7
-9 -6
-7 -9
2 -9
5 -7
0 -3
10
2 10
6 7
0 1
1 5
5 5
6...

output:

5.78434691777945746019
0.00000000000000000000
0.00000000000000000000
0.00000000000000000000
0.00000000000000000000
0.00000000000000000000
0.00000000000000000000
0.00000000000000000000
11.19071476564973179578
0.00000000000000000000
0.00074742358692975974
38.31115625262450659697
0.00000000000000000000...

result:

ok 100000 numbers

Test #7:

score: 0
Accepted
time: 825ms
memory: 4164kb

input:

10000
-7 -9 8 -2 -9
4 5
-8 -7
4 -9
5 8
-8 4
4 7
-7 2
0 -5
6 6
-6 9
3
8 10
4 6
2 5
-3 -2 10 10 -8
3 6
-9 0
-7 -6
4 7
5 9
-10 4
-6 -8
2 -8
-2 3
-8 4
2
2 5
6 10
-8 -7 9 2 5
4 2
-10 -4
9 -2
7 5
2 10
5 3
-8 6
-5 -9
9 -5
4 7
-4 7
1
8 8
-7 -7 10 7 7
4 5
-10 -8
6 -4
6 3
-2 8
4 8
-9 -9
8 8
6 8
-4 4
8
3 8
3 8...

output:

0.00000000000000000000
0.00000000000000000000
0.00000000000000000000
0.00000000000000000000
0.00000000000000000000
108.99283520875611319667
5.56525573192239858544
5.56525573192239858544
49.86435902335683447578
0.00000000000000000000
142.98614459298219980798
0.00000000000000000000
79.0723730210909698...

result:

ok 100000 numbers

Test #8:

score: 0
Accepted
time: 821ms
memory: 4020kb

input:

10000
7 -5 9 2 10
3 1
-2 2
9 -2
10 2
3 6
-10 -5
5 6
-5 10
1
5 5
-9 3 8 -9 -7
4 3
-10 -4
9 1
4 5
-8 8
3 7
-7 -2
9 -2
7 8
12
5 7
7 8
0 0
2 5
3 5
5 10
3 4
3 8
1 7
5 8
2 9
3 10
-5 0 9 -3 -8
5 4
-10 -2
3 -8
9 5
6 9
-5 8
4 8
-10 -3
6 -3
10 2
7 10
8
1 6
4 6
8 8
1 5
4 7
7 8
2 9
4 8
-10 -4 9 6 -5
5 5
3 -1
9 ...

output:

0.00000000000000000000
0.00000000000000000000
0.00000000000000000000
0.00000000000000000000
0.00000000000000000000
0.00000000000000000000
0.00000000000000000000
0.00000000000000000000
0.00000000000000000000
0.00000000000000000000
0.00000000000000000000
0.00000000000000000000
0.00000000000000000000
0...

result:

ok 100000 numbers

Test #9:

score: 0
Accepted
time: 848ms
memory: 4164kb

input:

10000
-8 -5 4 -1 5
3 1
-3 -8
0 -5
2 5
4 2
-5 -5
9 7
9 10
-2 8
10
1 6
4 5
3 10
1 6
1 2
1 3
0 4
9 9
6 8
1 3
8 3 5 8 2
5 1
-7 -8
3 -7
-1 -2
-5 1
-7 -7
4 4
-4 -3
-1 -7
7 -8
-1 7
12
3 7
8 8
9 10
4 5
6 8
1 8
0 5
2 9
5 8
5 5
0 0
2 7
-1 8 10 -9 -7
6 1
-3 -6
1 -8
6 -7
6 -5
0 6
-2 5
4 5
-7 8
-6 -7
5 -3
2 9
9
...

output:

6.12986040119844795369
0.00000000000000000000
0.02592592592592592617
6.12986040119844795369
19.98060033729057105925
15.23391026225537914218
11.08057812382077836431
0.00000000000000000000
0.00000000000000000000
15.23391026225537914218
0.00000000000000000000
0.00000000000000000000
0.000000000000000000...

result:

ok 100000 numbers

Test #10:

score: 0
Accepted
time: 843ms
memory: 4064kb

input:

10000
-2 -5 7 -3 6
3 2
-3 -7
9 -8
1 -7
5 5
-9 -10
6 -3
8 -1
-4 7
-5 4
4
1 5
6 10
8 10
0 4
6 -5 10 9 -3
6 4
-6 -8
1 -10
7 -6
3 4
-4 10
-6 -2
4 9
-7 -6
-2 -8
2 -8
10 6
8
4 7
2 10
0 1
2 2
2 8
3 9
0 3
0 5
-7 -5 9 8 7
3 4
-8 6
-2 4
6 3
4 5
-10 -9
-5 -8
-1 0
-6 -3
17
0 9
6 10
1 10
6 6
0 5
10 10
8 9
3 4
0 ...

output:

1.63741391694725028265
0.00000000000000000000
0.00000000000000000000
2.56572212272024478895
0.00000000000000000000
0.00000000000000000000
1.87681380010147133314
0.00000000000000000000
0.00000000000000000000
0.00000000000000000000
0.62560460003382377771
0.37536276002029426662
0.00000000000000000000
0...

result:

ok 100000 numbers

Test #11:

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

input:

10000
-7 -8 9 -1 5
5 6
-5 10
1 -5
9 -10
10 -1
-2 10
3 7
-8 -9
5 -7
-8 -1
5
2 5
0 2
8 10
6 8
0 4
-6 -3 10 1 -5
3 7
-10 -6
7 8
-1 7
4 8
-8 8
-4 6
8 6
2 7
1
8 8
1 -6 8 2 -4
3 1
-9 -9
7 -1
-6 7
4 2
-10 10
-5 6
4 1
8 1
6
7 9
3 6
9 9
2 10
8 10
1 2
0 -8 10 -10 -3
4 4
-4 -10
7 7
8 9
6 10
3 9
-8 0
8 -3
4 6
1...

output:

0.00000000000000000000
108.52193506923281147297
0.00000000000000000000
0.00000000000000000000
54.26096753461640573649
0.00000000000000000000
0.00000000000000000000
0.00000000000000000000
0.00000000000000000000
0.00000000000000000000
0.00000000000000000000
0.00000000000000000000
0.0000000000000000000...

result:

ok 100000 numbers

Test #12:

score: 0
Accepted
time: 826ms
memory: 4164kb

input:

10000
-5 3 9 -4 -1
3 2
-1 2
8 -3
0 10
3 8
-5 -5
10 -8
6 5
8
0 1
4 10
8 9
5 10
5 10
4 4
0 1
0 7
1 2 6 8 6
3 2
-9 -9
-3 -7
-4 10
4 5
-9 9
-5 1
-1 -5
6 9
2
3 9
1 5
-2 0 9 8 0
4 2
-5 -10
8 -9
9 3
-2 9
5 8
-10 1
-9 -3
7 -7
2 3
1 3
13
4 6
6 8
3 10
4 6
1 2
4 5
6 10
2 6
1 3
4 9
2 3
0 9
8 8
-10 -8 8 -2 -10
4...

output:

0.00000000000000000000
0.00000000000000000000
0.00000000000000000000
0.00000000000000000000
0.00000000000000000000
0.00000000000000000000
0.00000000000000000000
0.00000000000000000000
0.00000000000000000000
0.00000000000000000000
0.00000000000000000000
0.00000000000000000000
0.00000000000000000000
0...

result:

ok 100000 numbers

Test #13:

score: 0
Accepted
time: 765ms
memory: 4128kb

input:

3000
78 -37 984 -936 -370
9 158
-911 94
-338 -910
-20 -938
746 -972
922 -628
988 107
951 719
-94 936
-815 876
7 717
-960 -107
-231 -851
-112 -963
136 -970
979 99
565 655
-821 120
66
61 89
53 73
5 67
100 100
60 60
22 74
40 68
29 95
81 89
73 75
2 65
3 70
41 64
13 61
38 52
74 82
72 85
89 92
62 77
28 39...

output:

0.00000000000000000000
0.00000000000000000000
0.00000000000000000000
0.00000000000000000000
0.00000000000000000000
0.00000000000000000000
0.00000000000000000000
0.00000000000000000000
0.00000000000000000000
0.00000000000000000000
0.00000000000000000000
0.00000000000000000000
0.00000000000000000000
0...

result:

ok 100000 numbers

Test #14:

score: 0
Accepted
time: 770ms
memory: 4080kb

input:

3000
-67 75 588 514 -204
9 202
-942 678
-809 -376
-438 -910
-301 -967
827 -834
993 -83
1000 216
976 793
323 776
12 457
-982 -27
-923 -331
-851 -666
-297 -900
60 -944
884 -419
910 -275
751 478
182 984
-633 830
-863 783
-962 653
5
17 52
37 38
89 89
51 97
56 93
62 -58 758 475 38
6 695
-865 872
-439 -45...

output:

0.00000000000000000000
0.00000000000000000000
0.00000000000000000000
0.00000000000000000000
0.00000000000000000000
0.00000000000000000000
0.00000000000000000000
0.00000000000000000000
0.00000000000000000000
0.00000000000000000000
0.00000000000000000000
0.00000000000000000000
0.00000000000000000000
0...

result:

ok 100000 numbers

Test #15:

score: 0
Accepted
time: 764ms
memory: 4068kb

input:

3000
-58 -85 960 -15 286
12 387
-964 109
-899 -184
-109 -853
72 -904
953 -741
970 -497
991 397
857 779
830 852
699 968
-755 985
-959 527
8 596
-983 -850
-294 -923
842 -841
989 -207
976 635
724 935
-551 949
-980 927
6
36 66
77 87
29 51
55 99
70 89
79 89
-99 -7 795 556 995
6 442
-835 229
-752 -635
-24...

output:

0.00000000000000000000
0.00000000000000000000
0.00000000000000000000
0.00000000000000000000
0.00000000000000000000
0.00000000000000000000
0.00000000000000000000
0.00000000000000000000
0.00000000000000000000
0.00000000000000000000
0.00000000000000000000
0.00000000000000000000
0.00000000000000000000
1...

result:

ok 100000 numbers

Test #16:

score: 0
Accepted
time: 777ms
memory: 4300kb

input:

3000
75 84 988 574 -757
10 504
-967 -610
-882 -924
724 -893
793 -867
873 -595
985 -35
633 490
175 865
-851 935
-965 -353
7 765
-803 -198
-404 -915
221 -987
820 -755
933 359
809 908
-543 329
26
74 91
29 71
10 80
34 37
77 89
0 21
59 86
25 65
79 98
16 56
21 34
12 55
6 26
67 73
30 66
29 40
3 78
13 57
21...

output:

0.00000000000000000000
0.00000000000000000000
0.00000000000000000000
0.00000000000000000000
0.00000000000000000000
1196864.38143310098018901044
0.00000000000000000000
0.00000000000000000000
0.00000000000000000000
0.00000000000000000000
0.00000000000000000000
0.00000000000000000000
0.0000000000000000...

result:

ok 100000 numbers

Test #17:

score: 0
Accepted
time: 777ms
memory: 4288kb

input:

3000
-26 86 643 337 -777
8 449
-891 24
-831 -802
735 -975
879 -627
978 385
998 761
-523 930
-827 579
7 563
-791 -579
220 -766
484 -747
770 -607
942 456
929 959
-599 941
63
26 47
1 34
66 72
1 23
19 91
34 73
7 48
15 60
25 69
10 99
6 93
37 92
32 46
26 94
58 64
21 21
5 29
21 80
48 94
24 99
12 31
17 88
3...

output:

0.00000000000000000000
716454.45850988237538103931
0.00000000000000000000
1074681.68776482356304313726
0.00000000000000000000
0.00000000000000000000
0.00000000000000000000
0.00000000000000000000
0.00000000000000000000
0.00000000000000000000
0.00000000000000000000
0.00000000000000000000
0.00000000000...

result:

ok 100000 numbers

Test #18:

score: 0
Accepted
time: 768ms
memory: 4196kb

input:

3000
-62 -78 898 -314 288
6 168
-995 624
164 -897
849 -726
889 899
-14 886
-679 826
5 850
-891 -849
-707 -830
867 -141
665 881
-850 715
35
10 52
23 56
61 95
63 96
41 58
29 72
23 28
7 92
24 40
15 62
85 89
1 59
20 20
63 71
10 37
29 48
12 67
2 2
53 53
7 81
15 75
6 76
16 63
6 32
14 76
13 74
22 87
2 17
3...

output:

0.00000000000000000000
0.00000000000000000000
0.00000000000000000000
0.00000000000000000000
0.00000000000000000000
0.00000000000000000000
0.00000000000000000000
0.00000000000000000000
0.00000000000000000000
0.00000000000000000000
0.00000000000000000000
104457.29206843053265885146
0.00000000000000000...

result:

ok 100000 numbers

Test #19:

score: 0
Accepted
time: 777ms
memory: 4168kb

input:

3000
-1 40 801 18 45
10 245
-920 431
-743 -781
-403 -926
769 -887
960 -462
893 970
775 994
-132 970
-873 903
-904 853
10 690
-935 -206
-834 -359
164 -980
432 -915
865 -780
894 -669
1000 746
-36 778
-474 529
-908 -115
27
49 67
1 90
9 89
15 39
14 43
62 75
89 94
7 72
11 83
17 99
50 87
63 86
46 71
12 20...

output:

0.00000000000000000000
1457170.01110347617463958159
942960.62025431746667436528
1447882.60059499064243482280
1432062.02639415201554129453
0.00000000000000000000
0.00000000000000000000
1369225.69172786758292659215
859361.51775526946920535920
272620.83925177039887444153
0.00000000000000000000
0.000000...

result:

ok 100000 numbers

Test #20:

score: 0
Accepted
time: 775ms
memory: 4168kb

input:

3000
-37 -8 747 354 -861
11 228
-956 540
-880 -451
-824 -979
-113 -982
950 -978
907 371
799 750
728 914
69 940
-460 928
-824 844
10 255
-966 747
-897 -782
-817 -850
-662 -890
237 -977
936 -756
965 -624
999 115
741 762
-45 809
52
11 54
77 77
43 95
18 42
62 90
0 39
1 91
9 34
6 31
8 47
51 84
17 46
38 8...

output:

1422077.66330875884091256012
0.00000000000000000000
0.00000000000000000000
1358469.75780774768315950496
0.00000000000000000000
3228392.67551201831065554870
1325934.42889145127060146478
2777045.03305822825700488465
3338493.55017486590713815531
1961814.79234259831684994424
0.00000000000000000000
12436...

result:

ok 100000 numbers

Test #21:

score: 0
Accepted
time: 769ms
memory: 3972kb

input:

3000
48 -100 669 827 134
9 2
-985 -262
-952 -447
-241 -935
476 -920
742 -849
999 -527
992 781
12 898
-812 886
8 27
-988 459
-822 -477
-733 -682
-478 -990
659 -796
765 607
466 762
-708 662
46
1 9
13 96
74 83
86 86
31 81
76 95
28 68
52 78
73 93
16 92
7 52
57 85
51 82
80 99
56 80
22 65
73 86
2 33
69 69...

output:

2301237.84407539862240810180
397173.55418941577056557435
0.00000000000000000000
0.00000000000000000000
170724.78969380033203151470
0.00000000000000000000
284680.04895498427276834263
613.98646086525360049402
0.00000000000000000000
363900.37050995496437622023
1001711.55089086947828036500
0.00000000000...

result:

ok 100000 numbers

Test #22:

score: 0
Accepted
time: 771ms
memory: 4068kb

input:

3000
36 28 965 -40 913
8 290
-933 539
-647 -708
-94 -797
499 -690
844 169
802 576
-373 648
-928 639
6 400
-951 -965
884 -896
739 661
618 933
-789 995
-895 -255
53
66 98
1 30
0 25
77 77
2 4
27 62
62 91
92 96
33 69
17 100
66 66
17 67
18 27
48 80
16 47
17 90
45 96
14 61
15 82
81 85
86 89
22 82
70 85
67...

output:

0.00000000000000000000
801410.16223780327806025525
1098530.62298323177503789339
0.00000000000000000000
4041049.99403116354415033129
0.00000000000000000000
0.00000000000000000000
0.00000000000000000000
0.00000000000000000000
0.00000000000000000000
0.00000000000000000000
0.00000000000000000000
0.00000...

result:

ok 100000 numbers

Test #23:

score: 0
Accepted
time: 181ms
memory: 4200kb

input:

60
-2 -1 6 -692 -914
5 1
-39 64
14 -67
53 -14
59 5
37 51
7 5
-105 23
-63 -14
-24 -17
4 -19
12 -17
-16 23
-24 26
948
6 6
1 4
3 8
444 444
9 758
4 8
212 985
365 415
629 647
168 395
55 746
2 7
69 616
595 900
5 7
6 9
8 8
181 424
3 9
5 5
228 978
622 711
714 948
6 7
152 152
878 878
62 966
2 5
1 8
99 131
86...

output:

0.00000000000000000000
0.00000000000000000000
0.00000000000000000000
0.00000000000000000000
0.00000000000000000000
0.00000000000000000000
0.00000000000000000000
0.00000000000000000000
0.00000000000000000000
0.00000000000000000000
0.00000000000000000000
0.00000000000000000000
0.00000000000000000000
0...

result:

ok 100000 numbers

Test #24:

score: 0
Accepted
time: 225ms
memory: 4208kb

input:

60
2 -1 10 -9 -5
6 3
-64 -9
-25 -20
3 -16
26 7
-2 18
-41 14
118 8
-13458 1788
-13400 -150
-13174 -3448
-12376 -10187
-11659 -16224
-11423 -18192
-11178 -19459
-9694 -24458
-9018 -26389
-8654 -27421
-7753 -29655
-6590 -32133
-5887 -33359
-4543 -35667
-4092 -36278
-3268 -37365
-2246 -38667
-1091 -4006...

output:

4498.97959183673469851783
4498.97959183673468874787
4498.97959183673469496512
4498.97959183673469407694
4498.97959183673469407694
4498.97959183673469496512
4498.97959183673469851783
4498.97959183673469807374
4498.97959183673469496512
4498.97959183673469807374
4498.97959183673469851783
4498.979591836...

result:

ok 100000 numbers

Test #25:

score: 0
Accepted
time: 140ms
memory: 4352kb

input:

60
3 4 8 6 -6
8 4
-70 -8
-20 -7
33 11
35 58
33 75
-11 81
-48 63
-54 57
7 5
0 3
12 -7
34 -23
64 -42
79 -46
117 -27
80 24
3319
185 435
764 879
7 282
2 5
116 767
499 763
1 1
2 8
400 627
103 489
563 795
43 860
427 512
24 353
123 123
257 896
2 4
3 7
498 498
896 992
1 6
138 890
228 739
397 519
651 868
0 9...

output:

0.00000000000000000000
0.00000000000000000000
2069.54152809411087332592
1549.84383934847948049995
0.00000000000000000000
0.00000000000000000000
590.32271346810427020690
2196.02418164089362417890
0.00000000000000000000
0.00000000000000000000
0.00000000000000000000
183.60146647713914049016
0.000000000...

result:

ok 100000 numbers

Test #26:

score: 0
Accepted
time: 192ms
memory: 4244kb

input:

60
-10 4 99050 -3 6
7 26049
-45 27
53 -70
97 -112
110 -89
122 -47
123 -35
88 39
11 77577
-14 17
-11 -30
9 -80
52 -75
110 -65
143 -36
161 40
158 58
122 70
89 65
4 43
2233
161 663
162 922
6 8
889 963
232 251
661 739
818 971
7 10
287 999
1 6
5 9
0 3
466 749
277 277
4 10
236 442
871 925
2 9
207 843
374 ...

output:

0.00000000000000000000
0.00000000000000000000
13309.80493666504675687179
0.00000000000000000000
0.00000000000000000000
0.00000000000000000000
0.00000000000000000000
9522.14311798477765069748
0.00000000000000000000
20072.62688793973430811945
13269.48000261086059659021
22224.33696186162382879559
0.000...

result:

ok 100000 numbers

Test #27:

score: 0
Accepted
time: 221ms
memory: 4192kb

input:

60
-14255 85728 83963 -625 308
6 7088
-10 10
-8 -41
19 -75
119 -24
163 10
182 44
406 8385
-17623 -590
-17616 -755
-17575 -1522
-17432 -4162
-17366 -4990
-17355 -5120
-17302 -5701
-17280 -5928
-17188 -6832
-17103 -7636
-17051 -8062
-16943 -8925
-16884 -9331
-16757 -10203
-16742 -10303
-16725 -10408
-...

output:

13749.41602072315685312276
13749.41602072315685312276
13749.41602072315673588321
13749.41602072315685489912
13749.41602072315685489912
13749.41602072315685489912
13749.41602072315666394076
13749.41602072315685312276
13749.41602072315684779369
13749.41602072315685489912
13749.41602072315685401094
137...

result:

ok 100000 numbers

Test #28:

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

input:

60
6 1 98772 -10 0
9 50424
-173 -37
-50 -40
-35 -38
-31 -35
-8 21
-8 24
-13 95
-91 93
-158 90
252 60791
-46140 5792
-46125 3833
-46121 3699
-46025 1061
-45927 -1169
-45841 -2463
-45718 -3974
-45673 -4509
-45536 -6005
-45390 -7474
-45234 -8942
-45170 -9480
-44996 -10847
-44670 -12865
-44082 -15910
-4...

output:

82574.64650734889845296038
82574.64650734889846006581
82574.64650734889979588615
82574.64650734889846717124
82574.64650734889846006581
82574.64650734889801242389
82574.64650734889846717124
82574.64650734889846006581
82574.64650734889873007205
82574.64650734890047800718
82574.64650734889846717124
825...

result:

ok 100000 numbers

Test #29:

score: 0
Accepted
time: 179ms
memory: 4184kb

input:

60
-4177 -13751 89389 6 -9
6 23007
-90 -47
-26 -74
38 -85
76 41
38 52
-26 11
13 59759
-74 -6
-69 -30
-47 -32
-45 -32
-29 -31
11 -21
82 -2
74 20
57 29
52 31
-3 32
-49 31
-73 4
2743
376 815
158 554
31 497
566 652
134 242
1 7
103 680
8 8
1 9
191 530
190 190
465 526
380 957
1 10
929 987
1 1
2 5
267 817
...

output:

0.00000000000000000000
0.00000000000000000000
0.00000000000000000000
0.00000000000000000000
0.00000000000000000000
0.00000000000000000000
0.00000000000000000000
0.00000000000000000000
0.00000000000000000000
0.00000000000000000000
0.00000000000000000000
0.00000000000000000000
0.00000000000000000000
0...

result:

ok 100000 numbers

Test #30:

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

input:

60
10 -7 76710 1 -10
15 1799
-107 125
-97 40
-80 -29
-76 -35
-40 -34
-17 -30
-11 -28
7 -15
9 40
3 64
-13 113
-15 117
-21 126
-61 139
-96 145
14 4198
-108 39
-107 29
-101 10
-71 -27
-36 -62
1 -70
27 -52
51 -17
58 6
44 68
18 87
-26 83
-55 76
-106 60
3271
1 8
298 463
507 992
493 766
641 641
5 8
4 4
300...

output:

11344.03931317313459992135
6161.77438014548569666928
179.16115484652096598306
433.03894769675189174718
0.00000000000000000000
11400.03807693326101979636
11330.30620662422903333066
2416.38356241548641967221
11344.18472284102153047058
4888.43514416513748299664
1302.48352177296399101447
5021.5304362028...

result:

ok 100000 numbers

Test #31:

score: 0
Accepted
time: 205ms
memory: 4044kb

input:

60
85399 -87912 4 -5 2
6 1
-19 34
10 -4
44 -28
104 2
134 20
40 38
5 3
-122 -3
1 -23
61 -13
50 7
-10 79
229
714 801
683 855
3 10
42 609
3 6
5 5
98 637
0 10
0 6
7 8
665 995
4 6
337 664
3 8
374 855
637 637
143 318
6 8
27 365
287 327
4 5
41 960
1 3
154 820
73 394
18 636
0 5
859 880
4 8
382 470
491 840
6...

output:

0.00000000000000000000
0.00000000000000000000
0.00000000000000000000
0.00000000000000000000
0.00000000000000000000
0.00000000000000000000
0.00000000000000000000
0.00000000000000000000
0.00000000000000000000
0.00000000000000000000
0.00000000000000000000
0.00000000000000000000
0.00000000000000000000
0...

result:

ok 100000 numbers

Test #32:

score: 0
Accepted
time: 230ms
memory: 4312kb

input:

60
-10 7 7 1 5
6 1
-162 -58
-24 -49
-6 -7
-10 17
-24 36
-86 41
648 4
-23029 2131
-23020 1272
-23019 1186
-23017 1020
-23015 906
-23008 584
-22997 156
-22992 -27
-22984 -265
-22972 -592
-22943 -1360
-22914 -2016
-22903 -2230
-22896 -2363
-22847 -3242
-22811 -3860
-22741 -5008
-22710 -5485
-22692 -576...

output:

13636.97222222222227205890
13636.97222222222222232091
13636.97222222222222232091
13636.97222222222222320909
13636.97222222222222143273
13636.97222222222222232091
13636.97222222222222498544
13636.97222222222240262113
13636.97222222222222320909
13636.97222222222222676180
13636.97222222222222409727
136...

result:

ok 100000 numbers

Test #33:

score: 0
Accepted
time: 1094ms
memory: 4264kb

input:

60
15682 -4744 10 10 2
743 3
-15894 -2108
-15889 -2921
-15885 -3142
-15876 -3485
-15870 -3697
-15861 -3979
-15848 -4333
-15811 -5217
-15798 -5508
-15785 -5776
-15775 -5971
-15772 -6024
-15754 -6327
-15751 -6372
-15728 -6655
-15708 -6893
-15700 -6983
-15611 -7954
-15598 -8095
-15590 -8179
-15558 -851...

output:

0.00000000000000000000
0.00000000000000000000
0.00000000000000000000
0.00000000000000000000
0.00000000000000000000
0.00000000000000000000
0.00000000000000000000
0.00000000000000000000
0.00000000000000000000
0.00000000000000000000
0.00000000000000000000
0.00000000000000000000
0.00000000000000000000
0...

result:

ok 100000 numbers

Test #34:

score: 0
Accepted
time: 888ms
memory: 4228kb

input:

60
-8064 19156 8 6 0
728 2
-9570 256
-9569 -101
-9568 -313
-9559 -1075
-9556 -1302
-9551 -1625
-9540 -2015
-9537 -2112
-9532 -2260
-9520 -2581
-9519 -2605
-9501 -2996
-9499 -3039
-9486 -3312
-9482 -3388
-9456 -3758
-9437 -4025
-9412 -4331
-9405 -4407
-9315 -5328
-9261 -5813
-9237 -6025
-9232 -6069
-...

output:

1997087249.52672918944153934717
1997195902.05843275075312703848
1996978600.20696559688076376915
1996848106.03751217399258166552
1959497389.33303935162257403135
1997022081.13367482915055006742
1997195900.45246276678517460823
1985049143.00776368973311036825
1971255131.63099822448566555977
1955292374.6...

result:

ok 100000 numbers

Test #35:

score: 0
Accepted
time: 1085ms
memory: 4292kb

input:

60
16409 -38207 8 -5 2
744 1
-14468 -2661
-14467 -2844
-14466 -3006
-14465 -3132
-14459 -3703
-14456 -3918
-14454 -4054
-14451 -4254
-14448 -4408
-14432 -5131
-14419 -5604
-14415 -5743
-14409 -5942
-14408 -5972
-14406 -6029
-14404 -6085
-14368 -7053
-14352 -7450
-14329 -7995
-14311 -8406
-14293 -876...

output:

0.00000000000000000000
0.00000000000000000000
0.00000000000000000000
0.00000000000000000000
0.00000000000000000000
0.00000000000000000000
0.00000000000000000000
0.00000000000000000000
0.00000000000000000000
0.00000000000000000000
0.00000000000000000000
0.00000000000000000000
0.00000000000000000000
0...

result:

ok 100000 numbers

Test #36:

score: 0
Accepted
time: 1081ms
memory: 4280kb

input:

60
27332 65498 94576 -4 -10
689 4897
-7628 -631
-7626 -722
-7624 -801
-7617 -1002
-7613 -1070
-7609 -1133
-7608 -1145
-7604 -1189
-7595 -1281
-7592 -1309
-7577 -1421
-7559 -1555
-7556 -1572
-7533 -1661
-7521 -1706
-7507 -1755
-7486 -1825
-7469 -1880
-7457 -1911
-7443 -1946
-7422 -1997
-7339 -2195
-7...

output:

160563494.27438929618801921606
160510702.01350697129964828491
160500143.47854247388022486120
168053074.24529198148229625076
160584611.04327090033621061593
168327556.68780573370167985559
170603640.50513957228395156562
160595169.54060447390656918287
177793598.40054658924054820091
169560447.78734239195...

result:

ok 100000 numbers

Test #37:

score: 0
Accepted
time: 1024ms
memory: 4252kb

input:

60
-5 3 72675 -283 -74
739 14232
-10968 -3618
-10966 -4287
-10964 -4465
-10958 -4734
-10947 -5225
-10925 -5992
-10917 -6262
-10909 -6489
-10892 -6934
-10855 -7884
-10849 -8033
-10836 -8340
-10826 -8563
-10811 -8879
-10786 -9397
-10762 -9829
-10746 -10098
-10725 -10425
-10712 -10620
-10690 -10947
-10...

output:

3412605691.92353128688409924507
3364513364.64699777867645025253
5701557339.69379528658464550972
4745145647.63968637166544795036
5701394995.94717189762741327286
5701151837.17954069655388593674
5701520196.04089583456516265869
5540562065.01898073637858033180
4373902356.28902795305475592613
3409467708.8...

result:

ok 100000 numbers

Test #38:

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

input:

1
-100000 -100000 95539 1 1
4924 27493
-49998 -2337
-49997 -2614
-49996 -2812
-49995 -2999
-49994 -3146
-49993 -3280
-49992 -3405
-49991 -3524
-49989 -3741
-49988 -3846
-49987 -3941
-49986 -4034
-49985 -4124
-49983 -4289
-49982 -4371
-49980 -4527
-49978 -4679
-49976 -4826
-49975 -4897
-49973 -5035
-...

output:

0.00000000000000000000
0.00000000000000000000
0.00000000000000000000
0.00000000000000000000
0.00000000000000000000
0.00000000000000000000
0.00000000000000000000
0.00000000000000000000
0.00000000000000000000
0.00000000000000000000
0.00000000000000000000
0.00000000000000000000
0.00000000000000000000
0...

result:

ok 100000 numbers

Test #39:

score: 0
Accepted
time: 62ms
memory: 5048kb

input:

1
100000 100000 79129 -1 -1
1974 7644
-24991 -2249
-24990 -2309
-24989 -2368
-24988 -2423
-24987 -2474
-24986 -2522
-24984 -2614
-24983 -2659
-24981 -2735
-24980 -2772
-24979 -2808
-24978 -2842
-24977 -2875
-24974 -2971
-24970 -3095
-24966 -3215
-24964 -3273
-24963 -3301
-24962 -3327
-24958 -3427
-2...

output:

0.00000000000000000000
0.00000000000000000000
0.00000000000000000000
0.00000000000000000000
0.00000000000000000000
0.00000000000000000000
0.00000000000000000000
0.00000000000000000000
0.00000000000000000000
0.00000000000000000000
0.00000000000000000000
0.00000000000000000000
0.00000000000000000000
0...

result:

ok 100000 numbers

Test #40:

score: 0
Accepted
time: 133ms
memory: 5220kb

input:

1
-100000 100000 66194 1 -1
4800 11259
-99982 -37373
-99981 -37487
-99979 -37713
-99978 -37814
-99977 -37911
-99975 -38103
-99974 -38192
-99973 -38272
-99971 -38428
-99970 -38501
-99969 -38573
-99967 -38715
-99965 -38848
-99963 -38979
-99962 -39038
-99960 -39155
-99959 -39210
-99958 -39264
-99957 -3...

output:

3705213757.82090930943377315998
3679576489.68372567137703299522
3671089348.21308992803096771240
3674502015.92054217332042753696
3705213758.09809350967407226562
3685172897.28190475003793835640
3692742780.37903321441262960434
3680749261.01860840758308768272
3666710875.21550952224060893059
3676528921.8...

result:

ok 100000 numbers

Extra Test:

score: 0
Extra Test Passed