QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#372520 | #3025. Assimilation | SolitaryDream# | TL | 0ms | 0kb | C++17 | 3.8kb | 2024-03-31 14:40:34 | 2024-03-31 14:40:36 |
answer
#include <bits/stdc++.h>
using namespace std;
const int N = 2e6 + 10;
typedef pair<double, double> pdd;
pdd operator+(pdd a, pdd b) {
return pdd(a.first + b.first, a.second + b.second);
}
struct Line {
double k, c;
};
struct Convex {
vector<Line> line;
vector<double> cross;
void Push(double k, double c) {
line.push_back({k, c});
}
inline double CrossX(Line a, Line b) {
return -(a.c - b.c) / (a.k - b.k);
}
void Solve(vector<double> &sp) {
sort(line.begin(), line.end(), [](Line a, Line b) {
if (a.k == b.k) return a.c > b.c;
return a.k > b.k;
});
int top = 0;
for (int i = 1; i < line.size(); ++i) {
while (top >= 0) {
if (line[i].k == line[top].k) {
--top;
} else if (top >= 1 && CrossX(line[i], line[top - 1]) <= CrossX(line[top], line[top - 1])) {
--top;
} else break;
}
line[++top] = line[i];
}
line.resize(top + 1);
cross.resize(line.size() - 1);
for (int i = 0; i < cross.size(); ++i) cross[i] = CrossX(line[i], line[i + 1]);
}
pdd Get(double x) {
int p = lower_bound(cross.begin(), cross.end(), x) - cross.begin();
return {line[p].k, line[p].c};
}
void Clear() {
line.clear();
cross.clear();
}
} U, D, R, L;
vector<pair<double, double>> A;
namespace Seg {
double f[N];
int D;
inline void Init() {
D = A.size() + 2;
for (int i = 0; i < A.size(); ++i) {
f[D + i] = A[i].second;
}
for (int i = D - 1; i; --i) f[i] = max(f[i << 1], f[i << 1 | 1]);
}
inline double Ask(int x, int y) {
double ans = 0;
for (int l = N + x - 1, r = N + y + 1; l ^ r ^ 1; l >>= 1, r >>= 1) {
if (~l & 1) ans = max(ans, f[l ^ 1]);
if ( r & 1) ans = max(ans, f[r ^ 1]);
}
return ans;
}
}
inline double GetArea(double x) {
auto [k1, c1] = U.Get(x) + D.Get(x);
auto [k2, c2] = R.Get(x) + L.Get(x);
return (k1 * x + c1) * (k2 * x + c2);
}
int main() {
ios::sync_with_stdio(0);
cin.tie(0);
cout << fixed << setprecision(15);
int Case;
cin >> Case;
while (Case--) {
L.Clear(); R.Clear();
U.Clear(); D.Clear();
int n;
cin >> n;
for (int i = 1; i <= n; ++i) {
int x, y, u, v, dx, dy;
cin >> x >> y >> u >> v >> dx >> dy;
U.Push(dy, v); D.Push(-dy, -y);
R.Push(dx, u); L.Push(-dx, -x);
}
vector<double> sp;
U.Solve(sp); D.Solve(sp);
R.Solve(sp); L.Solve(sp);
for (int i = 0; i < n; ++i)
sort(sp.begin(), sp.end());
sp.erase(unique(sp.begin(), sp.end()), sp.end());
double last = 0;
A.clear();
A.push_back({0, GetArea(0)});
for (auto cur : sp) {
double mid = (last + cur) * 0.5;
auto [k1, c1] = U.Get(mid) + D.Get(mid);
auto [k2, c2] = R.Get(mid) + L.Get(mid);
if (k1 * k2 < 0) {
double x = -(k1 + k2) / (k1 * k2);
if (x >= last && x <= cur) A.push_back({x, GetArea(x)});
}
A.push_back({cur, GetArea(cur)});
}
Seg::Init();
int m;
cin >> m;
for (int i = 1; i <= m; ++i) {
double x, y;
cin >> x >> y;
double ans = max(GetArea(x), GetArea(y));
int p1 = lower_bound(A.begin(), A.end(), pdd(x, 0)) - A.begin();
int p2 = lower_bound(A.begin(), A.end(), pdd(y, 0)) - A.begin() - 1;
ans = max(ans, Seg::Ask(p1, p2));
cout << ans << '\n';
}
}
return 0;
}
詳細信息
Test #1:
score: 0
Time Limit Exceeded
input:
29 9 1 1 1 2 1 1 1 1 1 1 4 1 3 2 1 1 5 316660370 269357435 105688553 346785866 295093544 181703417 6 43402885 39947441 27068237 43810814 44913378 40095941 34779892 22 319594 3815194 3056481 6593888 7315914 6593888 4794774 2561877 5256242 4920603 5256242 3606645 864746 1594265 1235578 2361430 2277526...
output:
705096198511282342017825511571456.000000000000000 12104194479543555470845405548249088.000000000000000 11583562611393181188504076922388480.000000000000000 13433201433907587800813401433702400.000000000000000 11691113521781205716576204669059072.000000000000000 11691113521781205716576204669059072.000000...