QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#201580#6542. Optimal Quadratic Functionucup-team1209WA 1ms4040kbC++204.2kb2023-10-05 15:15:472023-10-05 15:15:48

Judging History

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

  • [2023-10-05 15:15:48]
  • 评测
  • 测评结果:WA
  • 用时:1ms
  • 内存:4040kb
  • [2023-10-05 15:15:47]
  • 提交

answer

#include<bits/stdc++.h>
const int N = 300005;
const int mod = 1e9 + 7;
using ll = long long;
using pr = std::pair<int, int>;
using std::cin;
using std::cout;
using f128 = __float128;
using db = long double;
struct vec2 {
	db x, y;
	db abs() const {
		return sqrt(x * x + y * y);
	}
};
const db eps = 1e-8;
int sgn(db x, db eps = ::eps) {
	return x < -eps ? -1 : x > eps;
}
vec2 operator + (vec2 x, vec2 y) { return {x.x + y.x, x.y + y.y}; }
vec2 operator - (vec2 x, vec2 y) { return {x.x - y.x, x.y - y.y}; }
vec2 operator / (vec2 x, db y) { return {x.x / y, x.y / y}; }
db operator * (vec2 x, vec2 y) { return x.x * y.y - x.y * y.x; }
db operator % (vec2 x, vec2 y) { return x.x * y.x + x.y * y.y; }
int half(vec2 x) { return x.y < -eps || (sgn(x.y) == 0 && x.x <= eps); }
int cmp(vec2 a, vec2 b) { return half(a) == half(b) ? a * b > 0 : half(b); }
struct line : vec2 {
	f128 z;
	db operator () (vec2 t) const {
		return t % vec2{*this} + z;
	}
	void reduce() {
		db w = abs();
		x /= w;
		y /= w;
		z /= w;
	}
};
vec2 operator & (line x, line y) {
	return vec2{vec2{x.z, x.y} * vec2{y.z, y.y}, vec2{x.x, x.z} * vec2{y.x, y.z}} / -(vec2(x) * vec2(y));
}
f128 det(line a, line b, line c) {
	vec2 A = a, B = b, C = c;
	return c.z * f128(A * B) + a.z * f128(B * C) + b.z * f128(C * A);
}
bool is_para(line x, line y) { return sgn(vec2(x) * vec2(y)) == 0; }
db check(line a, line b, line c) {
	return sgn(det(a, b, c), 2e-7) * sgn(vec2(a) * vec2(b));
}
bool paraS(line a, line b) {
	return is_para(a, b) && vec2(a) % vec2(b) > 0;
}
db dist(line l) {
	return l.z / l.abs();
}
std::vector<vec2> HPI(std::vector<line> vs) {
	auto cmp = [](line a, line b) -> bool {
		if(paraS(a, b)) return dist(a) < dist(b);
		return ::cmp(vec2(a), vec2(b));
	};
	sort(vs.begin(), vs.end(), cmp);
	int ah = 0, at = 0, n = size(vs);
	std::vector<line> deq(n + 1);
	std::vector<vec2> ans(n);
	deq[0] = vs[0];
	for(int i = 1;i <= n;++i) {
		line o = i < n ? vs[i] : deq[ah];
		if(paraS(vs[i - 1], o)) {
			continue;
		}
		for(;ah < at && check(deq[at - 1], deq[at], o) < 0;) -- at;
		if(i != n)
		for(;ah < at && check(deq[ah], deq[ah + 1], o) < 0;) ++ ah;
		if(!is_para(o, deq[at])) {
			ans[at] = o & deq[at];
			deq[++at] = o;
		}
	}
	if(at - ah <= 2) return {};
	std::vector<vec2> ret = {ans.begin() + ah, ans.begin() + at};
	return ret;
}
struct ob { db x, y, z; f128 w; };
std::mt19937 gen(3);
bool solve(std::vector<ob> & o) {
	shuffle(o.begin(), o.end(), gen);
	const db V = 1e12;
	db a = -V, b = -V, c = -V;
	for(int i = 0;i < (int) o.size();++i) {
		auto [x, y, z, w] = o[i];
		if(a * x + b * y + c * z <= w + eps) {
			continue;
		}
		static std::vector<line> v;
		v = {
			{V, 0, V * V}, {0, V, V * V},
			{-V, 0, V * V}, {0, -V, V * V},
		};
		for(int j = 0;j < i;++j) {
			auto [X, Y, Z, W] = o[j];
			if(z == Z) {
				X -= x;
				Y -= y;
				W -= w;
			} else {
				X += x;
				Y += y;
				W += w;
			}
			if(sgn(X) || sgn(Y)) {
				v.push_back({-X, -Y, W});
				v.back().reduce();
			} else {
				if(W < -eps) return 0;
			}
		}
		auto res = HPI(v);
		if(res.empty()) return 0;
		a = res[0].x;
		b = res[0].y;
		for(int i = 1;i < (int) res.size();++i) {
			auto [x, y] = res[i];
			if(x < a - eps || sgn(x - a) == 0 && y < b) {
				a = x;
				b = y;
			}
		}
		c = (w - x * a - y * b) / z;
		for(int j = 0;j <= i;++j) {
			auto [X, Y, Z, W] = o[j];

			if(a * X + b * Y + c * Z > W + 0.001) {
				// assert(a * X + b * Y + c * Z <= W + 0.001);
			}
		}
	}
	return 1;
}
int main() {
#ifdef zqj
	freopen("$.in", "r", stdin);
#endif
	std::ios::sync_with_stdio(false), cin.tie(0);
	int T = 0;
	cin >> T;
	for(int i = 0;i < T;++i) {
		int n; cin >> n;
		std::vector<vec2> a(n);
		std::vector<db> y(n);
		for(int i = 0;i < n;++i) {
			long long x, Y; cin >> x >> Y; y[i] = Y;
			a[i] = {x * x, x};
		}
		db l = 0, r = 1e6;
		for(int i = 0;i < 45;++i) {
			db mid = (l + r) / 2;
			static std::vector<ob> L; L.clear();
			for(int i = 0;i < n;++i) {
				L.push_back({a[i].x, a[i].y, 1, y[i] + mid});
				L.push_back({-a[i].x, -a[i].y, -1, -y[i] + mid});
			}
			if(solve(L)) {
				r = mid;
			} else {
				l = mid;
			}
		}
		long double ans = (l + r) / 2;
		printf("%.10Lf\n", ans * ans);
	}
}

详细

Test #1:

score: 0
Wrong Answer
time: 1ms
memory: 4040kb

input:

1
4
0 0
1 3
2 9
3 0

output:

5.0624869928

result:

wrong answer 1st numbers differ - expected: '5.0625000', found: '5.0624870', error = '0.0000026'