QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#372592 | #3035. Ghost | SolitaryDream# | AC ✓ | 2930ms | 16156kb | C++17 | 4.3kb | 2024-03-31 16:03:13 | 2024-03-31 16:03:14 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
#define double long double
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);
}
inline bool Check(Line a, Line b, Line c) {
// return -(b.c - a.c) / (b.k - a.k) <= -(c.c - a.c) / (c.k - a.k);
long long X1 = -(b.c - a.c);
long long Y1 = (b.k - a.k);
long long X2 = -(c.c - a.c);
long long Y2 = (c.k - a.k);
int rst = X1 * Y2 <= X2 * Y1;
if (Y1 < 0) rst ^= 1;
if (Y2 < 0) rst ^= 1;
return rst;
}
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 && Check(line[top - 1], line[i], line[top])) {
--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]);
for (auto x : cross) if (x > 0) sp.push_back(x);
}
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) {
if (x > y) return 0;
double ans = 0;
for (int l = D + x - 1, r = D + 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 max<double>(k1 * x + c1, 0.) * max<double>(k2 * x + c2, 0.);
}
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;
sp.push_back(1e6);
U.Solve(sp); D.Solve(sp);
R.Solve(sp); L.Solve(sp);
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);
double x = -(k1 * c2 + k2 * c1) * 0.5 / (k1 * k2);
if (x >= last && x <= cur) A.push_back({x, GetArea(x)});
A.push_back({cur, GetArea(cur)});
last = 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;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 940ms
memory: 4088kb
input:
4000 2 -5 -5 3 1 1 -5 -3 -4 -1 2 -2 1 169 4.5924 9.7635 4.9674 5.3219 8.2418 9.6649 6.5743 8.6108 5.3524 6.4199 2.1932 4.3636 1.7115 6.6926 0.5762 4.0628 5.0348 7.5678 6.2170 6.3381 7.1571 8.0276 1.7285 2.3730 0.3843 2.9644 0.0038 0.3971 3.8448 9.7040 4.0458 9.4878 1.6425 7.9132 8.9195 9.4455 4.2563...
output:
0.000000000000000 0.000000000000000 0.000000000000000 0.000000000000000 0.000000000000000 0.000000000000000 0.000000000000000 3.085600000000000 0.000000000000000 0.000000000000000 0.000000000000000 0.000000000000000 5.388400000000000 9.954400000000000 0.000000000000000 0.000000000000000 0.0000000000...
result:
ok OK!
Test #2:
score: 0
Accepted
time: 2930ms
memory: 9420kb
input:
49 20119 453553 453553 999314 999117 128392 128392 625880 625880 999937 999372 -124296 -124296 -34395 -34395 999431 999379 617841 617841 773531 773531 999210 999826 -458742 -458742 -351946 -351946 999501 999848 827822 827822 751364 751364 999088 999855 -391959 -391959 698502 698502 999908 999195 -26...
output:
28458932215.126596050336957 26610127672.555073169991374 28532937150.676446726545691 28532937150.676446726545691 28232156121.935278080403805 28014514974.478361969813704 26633365234.957375001162291 28014514974.478361969813704 28532937150.676446726545691 27190169607.005666369572282 26644935633.67628928...
result:
ok OK!
Test #3:
score: 0
Accepted
time: 1466ms
memory: 16156kb
input:
11 2437 -319663 -890371 927261 655392 1 3 -257629 -963537 454576 973758 5 -6 -143353 -761004 767384 895313 1 -4 -474255 -62583 604311 925105 -5 -7 -129789 -629223 875141 641849 3 6 -54357 -600036 845387 199014 2 3 -946287 -251448 306995 217922 7 -3 -480329 -265842 271418 189372 5 -4 -352502 -775709 ...
output:
64584.375000000000000 64584.375000000000000 64584.375000000000000 56289.635964240000000 37538.986472639999999 64584.375000000000000 64584.375000000000000 64584.375000000000000 64584.375000000000000 47531.486884560000004 63419.838128639999997 49064.913896639999997 20520.108799439999999 64584.37500000...
result:
ok OK!