QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#201608#6542. Optimal Quadratic Functionucup-team1209WA 4620ms4320kbC++204.0kb2023-10-05 15:27:382023-10-05 15:27:39

Judging History

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

  • [2023-10-05 15:27:39]
  • 评测
  • 测评结果:WA
  • 用时:4620ms
  • 内存:4320kb
  • [2023-10-05 15:27:38]
  • 提交

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 = f128;
struct vec2 {
	db x, y;
	db abs() const {
		return sqrt(x * x + y * y);
	}
};
const db eps = 1e-9;
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), 1e-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 && o(ans[at - 1]) < 1e-10;) -- at;
		if(i != n)
		for(;ah < at && o(ans[ah]) < 1e-10;) ++ 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 + 2e-7) {
			continue;
		}
		static std::vector<line> v;
		v = {
			{1, 0, V}, {0, 1, V},
			{-1, 0, V}, {0, -1, 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;
	}
	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 / 1e3, 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: 100
Accepted
time: 2ms
memory: 3824kb

input:

1
4
0 0
1 3
2 9
3 0

output:

5.0625000384

result:

ok found '5.0625000', expected '5.0625000', error '0.0000000'

Test #2:

score: -100
Wrong Answer
time: 4620ms
memory: 4320kb

input:

60
1
1000 -990
2
171 -638
949 -99
2
633 227
-257 -602
3
634 -994
633 999
-374 995
3
445 -110
586 -121
462 29
9
-995 -224
-458 -833
691 -670
456 -259
-376 55
-563 -12
834 827
-826 -220
299 744
17
997 991
997 976
997 988
998 -986
999 -982
999 -980
999 -996
998 -988
998 -991
997 987
1000 996
999 -1000
...

output:

0.0000000000
0.0000000000
0.0000000000
0.0000000000
0.0000000000
543160.1260095665
120.9999990764
0.8320062933
412780.6071849340
12.2499994408
15750.2500025081
118751.3800964622
880245.5055054216
1.0000000234
15.3633734811
854986.7131146983
20.2500007930
24567.6673704805
881031.5630356103
306.250002...

result:

wrong answer 22nd numbers differ - expected: '0.0000000', found: '0.0014425', error = '0.0014425'