QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#464480 | #8214. Huge Oil Platform | ucup-team3215 | WA | 1ms | 3920kb | C++23 | 4.3kb | 2024-07-06 09:57:13 | 2024-07-06 09:57:13 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using ld = double;
template<class T>
int sgn(T x) { return (x > 0) - (x < 0); }
template<class T>
struct Point {
typedef Point P;
T x, y;
explicit Point(T x = 0, T y = 0) : x(x), y(y) {}
template<typename U>
explicit Point(Point<U> o) : x(o.x), y(o.y) {};
bool operator<(P p) const { return tie(x, y) < tie(p.x, p.y); }
bool operator==(P p) const { return tie(x, y) == tie(p.x, p.y); }
P operator+(P p) const { return P(x + p.x, y + p.y); }
P operator-(P p) const { return P(x - p.x, y - p.y); }
P operator*(T d) const { return P(x * d, y * d); }
P operator/(T d) const { return P(x / d, y / d); }
T dot(P p) const { return x * p.x + y * p.y; }
T cross(P p) const { return x * p.y - y * p.x; }
T cross(P a, P b) const { return (a - *this).cross(b - *this); }
T dist2() const { return x * x + y * y; }
ld dist() const { return sqrtl(dist2()); }
P unit() const { return *this / dist(); } // makes dist()=1
P perp() const { return P(-y, x); } // rotates +90 degrees
// returns point rotated 'a' radians ccw around the origin
P rotate(double a) const {
return P(x * cos(a) - y * sin(a), x * sin(a) + y * cos(a));
}
friend ostream &operator<<(ostream &os, P p) {
return os << "(" << p.x << "," << p.y << ")";
}
};
struct s_tr {
const vector<pair<ld, int>> &all;
vector<array<ld, 6>> s;
s_tr(const vector<pair<ld, int>> &all) : all(all) {
ll n = all.size();
s.resize(4 * n, array<ld, 6>{});
}
auto combine(const array<ld, 6> &lhs, const array<ld, 6> &rhs) {
array<ld, 6> res{};
res[3] = rhs[3] + lhs[3];
res[2] = max(rhs[2], rhs[3] + lhs[2]);
res[1] = max(lhs[1], lhs[3] + rhs[1]);
res[4] = max(lhs[4], lhs[3] + rhs[4]);
res[5] = max(rhs[5], rhs[3] + lhs[5]);
res[0] = max({lhs[0], rhs[0], rhs[4] + lhs[5]});
return res;
}
void upd(int v, int l, int r, int k, ld val) {
if (l + 1 == r) {
s[v][3] = s[v][2] = s[v][1] = s[v][0] = val;
s[v][4] = val - 2 * all[l].first;
s[v][5] = val + 2 * all[l].first;
return;
}
int m = (r + l) / 2;
if (k < m)upd(v * 2 + 1, l, m, k, val);
else upd(v * 2 + 2, m, r, k, val);
s[v] = combine(s[v * 2 + 1], s[v * 2 + 2]);
}
};
template<typename P>
P lineProj(P a, P b, P p, bool refl = false) {
P v = b - a;
return p - v.perp() * (1 + refl) * v.cross(p - a) / v.dist2();
}
int main() {
cin.tie(0)->sync_with_stdio(false);
int n;
cin >> n;
vector<Point<ll>> a(n);
vector<ll> w(n);
for (int i = 0; i < n; ++i) {
cin >> a[i].x >> a[i].y >> w[i];
}
ld res{0};
for (int i = 0; i < n; ++i) {
auto v = a;
for (auto &x: v)x = x - a[i];
Point<ld> A(v[i]);
for (int j = i + 1; j < n; ++j) {
Point<ld> B(v[j]);
auto solve = [&](bool inv) {
vector<pair<ld, ll>> points;
vector<pair<ld, int>> all;
for (int k = 0; k < n; ++k) {
Point<ld> C(v[k]);
if ((inv ? -1 : 1) * v[j].cross(v[k]) >= 0) {
auto z = lineProj(A, B, C);
all.emplace_back(z.dist() * ((v[j]).dot(v[k]) < 0 ? -1 : 1), k);
points.push_back({(z - C).dist(), k});
}
}
sort(all.begin(), all.end());
vector<int> pos(n);
for (int j = 0; j < all.size(); ++j) {
pos[all[j].second] = j;
}
sort(points.begin(), points.end());
int N = all.size();
s_tr tree(all);
for (auto [d, k]: points) {
int p = pos[k];
tree.upd(0, 0, N, p, w[k]);
res = max(res, -2 * d + tree.s[0][0]);
}
};
solve(false);
solve(true);
}
}
cout << fixed << setprecision(20);
cout << res;
}
詳細信息
Test #1:
score: 100
Accepted
time: 0ms
memory: 3920kb
input:
2 1 1 1 3 3 1
output:
1.00000000000000000000
result:
ok found '1.0000000', expected '1.0000000', error '0.0000000'
Test #2:
score: 0
Accepted
time: 0ms
memory: 3856kb
input:
3 4 5 5 4 6 7 1 3 8
output:
10.10050506338833464781
result:
ok found '10.1005051', expected '10.1005051', error '0.0000000'
Test #3:
score: 0
Accepted
time: 0ms
memory: 3780kb
input:
2 0 0 1 1000000 1000000 1000000000
output:
1000000000.00000000000000000000
result:
ok found '1000000000.0000000', expected '1000000000.0000000', error '0.0000000'
Test #4:
score: -100
Wrong Answer
time: 1ms
memory: 3872kb
input:
20 328 207 21 365 145 188 347 79 41 374 335 699 288 250 97 32 267 131 296 332 434 2 91 36 139 43 21 26 455 696 57 135 410 14 500 396 255 181 646 103 114 593 309 351 787 207 316 138 440 416 806 413 349 695 413 201 501 455 396 442
output:
6507.62850931608045357279
result:
wrong answer 1st numbers differ - expected: '6092.4427126', found: '6507.6285093', error = '0.0681477'