QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#201580 | #6542. Optimal Quadratic Function | ucup-team1209 | WA | 1ms | 4040kb | C++20 | 4.2kb | 2023-10-05 15:15:47 | 2023-10-05 15:15:48 |
Judging History
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'