QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#338399 | #5570. Epidemic Escape | ucup-team1198 | WA | 166ms | 5856kb | C++20 | 8.6kb | 2024-02-25 21:18:45 | 2024-02-25 21:18:45 |
Judging History
answer
#pragma GCC optimize("fast-math,Ofast,unroll-loops")
#include <map>
#include <set>
#include <array>
#include <cmath>
#include <deque>
#include <bitset>
#include <random>
#include <string>
#include <vector>
#include <cassert>
#include <complex>
#include <iomanip>
#include <iostream>
#include <algorithm>
#include <unordered_map>
#include <unordered_set>
using namespace std;
#define int int64_t
using ld = __float128;
ld abs(ld x) {
if (x > 0) return x;
return -x;
}
struct IVector {
int x;
int y;
IVector(int x = 0, int y = 0): x(x), y(y) {}
IVector(const IVector& a, const IVector& b): x(b.x - a.x), y(b.y - a.y) {}
};
IVector operator-(const IVector& a) {
return {-a.x, -a.y};
}
int operator%(const IVector& a, const IVector& b) {
return a.x * b.y - a.y * b.x;
}
bool hp(const IVector& v) {
if (v.y == 0) return v.x > 0;
return v.y > 0;
}
bool operator<(const IVector& a, const IVector& b) {
if (hp(a) != hp(b)) return hp(a);
return a % b > 0;
}
bool operator==(const IVector& a, const IVector& b) {
return a.x == b.x && a.y == b.y;
}
istream& operator>>(istream& in, IVector& v) {
in >> v.x >> v.y;
return in;
}
const int MAXN = 1e5 + 100;
bool is_bad[MAXN];
struct Vector {
ld x;
ld y;
Vector(ld x = 0, ld y = 0): x(x), y(y) {}
Vector(const Vector& a, const Vector& b): x(b.x - a.x), y(b.y - a.y) {}
Vector(const IVector& a): x(a.x), y(a.y) {}
Vector(const IVector& a, bool inv) {
ld ln = a.x * a.x + a.y * a.y;
x = a.x; y = a.y;
x /= ln;
y /= ln;
}
ld sqlen() const { return x * x + y * y; }
};
Vector operator-(const Vector& a, const Vector& b) {
return Vector(b, a);
}
Vector operator+(const Vector& a, const Vector& b) {
return {a.x + b.x, a.y + b.y};
}
ld operator%(const Vector& a, const Vector& b) {
return a.x * b.y - a.y * b.x;
}
ld operator*(const Vector& a, const Vector& b) {
return a.x * b.x + a.y * b.y;
}
const ld EPS = 1e-32;
const int MAXK = 5;
vector<Vector> convex(vector<Vector>& p) {
if (p.empty()) return p;
if ((int)p.size() == 1) {
vector<Vector> p1 = p;
p.clear();
return p1;
}
int n = p.size();
Vector minp = p[0];
for (int i = 1; i < n; ++i) {
if (p[i].x < minp.x) {
minp = p[i];
} else if (p[i].x == minp.x && p[i].y < minp.y) {
minp = p[i];
}
}
sort(p.begin(), p.end(), [&](const Vector& u, const Vector& v) {
if (abs((u - minp) % (v - minp)) < EPS) {
return (u - minp).sqlen() < (v - minp).sqlen();
}
return (u - minp) % (v - minp) < 0;
});
bool online = true;
for (int i = 2; i < n; ++i) {
online &= abs((p[i] - p[0]) % (p[i] - p[1])) < EPS;
}
if (online) {
sort(p.begin(), p.end(), [&](const Vector& u, const Vector& v) {
return (u - minp).sqlen() < (v - minp).sqlen();
});
vector<Vector> st = {p[0], p.back()};
p.pop_back();
reverse(p.begin(), p.end());
p.pop_back();
return st;
}
p.push_back(p[0]);
/**for (auto elem : p) {
cout << (double)elem.x << " " << (double)elem.y << " : ";
}
cout << endl;*/
vector<Vector> st;
int sz = 0;
vector<Vector> p1;
for (auto v : p) {
while (sz >= 2 && (st[sz - 1] - st[sz - 2]) % (v - st[sz - 1]) >= -EPS) {
p1.push_back(st.back());
st.pop_back();
--sz;
}
st.push_back(v);
++sz;
}
st.pop_back();
p = p1;
return st;
}
vector<Vector> get_bst(const Vector& dir, const vector<Vector>& p, int cnt) {
if (p.empty()) return p;
int n = p.size();
int k = 0;
while ((1 << k) < n) ++k;
int i = 0;
while (k >= 0) {
int i1 = (i + (1 << k)) % n;
int i2 = (i - (1 << k) + 2 * n) % n;
if (dir * p[i1] > dir * p[i]) i = i1;
if (dir * p[i2] > dir * p[i]) i = i2;
--k;
}
vector<Vector> ans = {p[i]};
int sz = min(cnt - 1, n - 1);
int t1 = (i + 1) % n;
int t2 = (i - 1 + n) % n;
for (int _ = 0; _ < sz; ++_) {
if (dir * p[t1] > dir * p[t2]) {
ans.push_back(p[t1]);
t1 = (t1 + 1) % n;
} else {
ans.push_back(p[t2]);
t2 = (t2 - 1 + n) % n;
}
}
return ans;
}
mt19937 rnd;
const int MAX = 100000000;
signed main() {
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
cout << fixed << setprecision(10);
int n;
cin >> n;
vector<IVector> p(n);
int cnt0 = 0;
for (int i = 0; i < n; ++i) {
cin >> p[i];
/**p[i].x = rnd() % (2 * MAX) - MAX;
p[i].y = rnd() % (2 * MAX) - MAX;*/
}
vector<IVector> p1;
for (int i = 0; i < n; ++i) {
if (p[i] == IVector()) {
++cnt0;
} else {
p1.push_back(p[i]);
}
}
p = p1;
n = p.size();
int q;
cin >> q;
vector<pair<IVector, int>> qu(q);
for (int i = 0; i < q; ++i) {
cin >> qu[i].first >> qu[i].second;
/**qu[i].first.x = rnd() % (2 * MAX) - MAX;
qu[i].first.y = rnd() % (2 * MAX) - MAX;
qu[i].second = 5;*/
qu[i].second -= cnt0;
}
int cnt = 0;
for (int i = 0; i < n; ++i) {
if (hp(p[i])) ++cnt;
}
vector<pair<IVector, int>> ev;
for (int i = 0; i < n; ++i) {
ev.push_back({p[i], -1});
ev.push_back({-p[i], q});
}
for (int i = 0; i < q; ++i) {
if (qu[i].first == IVector()) {
is_bad[i] = true;
continue;
}
ev.push_back({{qu[i].first.y, -qu[i].first.x}, i});
}
sort(ev.begin(), ev.end());
for (auto elem : ev) {
if (elem.second == -1) {
--cnt;
} else if (elem.second == q) {
++cnt;
} else {
if (cnt < qu[elem.second].second) {
is_bad[elem.second] = true;
}
}
}
vector<Vector> pv;
for (int i = 0; i < n; ++i) {
pv.push_back(Vector(p[i], true));
/// cerr << i << ": " << (double)pv[i].x << " " << (double)pv[i].y << endl;
}
vector<vector<Vector>> hulls;
for (int i = 0; i < MAXK; ++i) {
hulls.push_back(convex(pv));
/**for (Vector v : hulls.back()) {
cout << (double)v.x << " " << (double)v.y << "; ";
}
cout << endl;*/
}
for (int i = 0; i < q; ++i) {
if (is_bad[i]) {
cout << "-1\n";
continue;
}
if (qu[i].second <= 0) {
cout << "0\n";
continue;
}
int k = qu[i].second;
Vector dir = qu[i].first;
vector<Vector> bst;
for (int i = 0; i < k; ++i) {
auto res = get_bst(dir, hulls[i], k - i);
/**vector<Vector> bst1;
int f1 = 0, f2 = 0;
for (int i = 0; i <= k && i < (int)bst.size() + res.size(); ++i) {
if (f2 >= res.size()) {
bst1.push_back(bst[f1++]);
} else if (f1 >= bst.size()) {
bst1.push_back(res[f2++]);
} else if (bst[f1] * dir > res[f2] * dir) {
bst1.push_back(bst[f1++]);
} else {
bst1.push_back(res[f2++]);
}
}
bst = move(bst1);*/
for (auto elem : res) {
bst.push_back(elem);
for (int i = (int)bst.size() - 1; i > 0; --i) {
if (dir * bst[i] > dir * bst[i - 1]) {
swap(bst[i], bst[i - 1]);
} else {
break;
}
}
if ((int)bst.size() > k) bst.pop_back();
}
}
long double ans = dir * bst[k - 1];
/// cout << (double)bst[k - 1].x << " " << (double)bst[k - 1].y << endl;
ans /= sqrtl(dir.x * dir.x + dir.y * dir.y);
ans = 0.5 / ans;
cout << ans << "\n";
if (ans < -1) {
cout << n << "\n";
for (int i = 0; i < n; ++i) {
cout << p[i].x << " " << p[i].y << "\n";
}
cout << qu[i].first.x << " " << qu[i].first.y << " " << qu[i].second << endl;
return 0;
}
}
return 0;
}
详细
Test #1:
score: 100
Accepted
time: 1ms
memory: 3980kb
input:
5 5 -3 5 4 -6 2 -5 0 4 1 2 -3 -10 1 6 -9 1
output:
8.7002554241 3.2260195623
result:
ok 2 numbers
Test #2:
score: 0
Accepted
time: 0ms
memory: 3840kb
input:
8 4 -1 4 -8 0 9 4 -7 -5 -2 5 -5 7 5 -9 2 10 4 -8 1 7 -7 5 -10 8 2 -9 9 2 4 -7 5 -1 -10 2 6 -3 2 2 -9 3 -10 -10 1 5 9 1
output:
3.1677629681 26.1629509039 5.4614883202 6.3639610307 -1 5.2894082216 3.7267799625 4.6097722286 2.9294423792 4.7617289402
result:
ok 10 numbers
Test #3:
score: 0
Accepted
time: 0ms
memory: 4068kb
input:
5 -4 -7 5 0 2 4 -7 -7 4 4 20 0 -5 2 -4 -7 2 -7 7 3 4 -4 3 -7 4 3 4 -4 1 2 4 1 6 -7 2 4 -4 2 4 4 3 5 4 1 -1 9 2 8 9 3 4 -4 2 6 3 3 -10 -3 2 -7 7 1 9 -4 1 -4 -7 3 -2 0 2
output:
7.0000000000 5.1305276580 -1 -1 -1 3.5355339059 2.2360679775 11.9854077945 15.3206469257 3.5355339059 2.4627400913 4.5276925691 3.7629983059 15.3206469257 2.9814239700 5.6217035048 7.0710678119 2.7357938338 -1 8.1250000000
result:
ok 20 numbers
Test #4:
score: 0
Accepted
time: 1ms
memory: 4024kb
input:
100 63 -48 20 -62 -81 -31 -17 -93 2 -74 72 25 -71 37 -71 17 56 67 -47 65 -89 14 62 30 -71 -33 14 -53 -57 -52 30 80 -14 -69 -45 -19 -54 -71 58 -20 -57 12 5 -56 -76 -2 26 61 24 60 10 -97 -63 38 17 81 -43 -38 44 35 -86 37 62 72 77 11 41 29 14 81 77 55 -54 -33 -43 -51 76 14 55 47 43 24 69 -13 16 75 11 9...
output:
26.7586788688 29.5714059979 24.6221445045 27.7717456547 26.6783667129 24.4237024605 28.8933481964 29.7761695578 31.9403629705 27.2149016024 31.7280950457 27.0711605517 25.2991100306 26.8710651521 28.9958394534 28.3563142462 29.9872588920 25.6496237196 25.1496681332 28.3011569706 28.6117519545 26.690...
result:
ok 100 numbers
Test #5:
score: -100
Wrong Answer
time: 166ms
memory: 5856kb
input:
10000 -3 3 -6 2 -4 1 -2 -5 5 -6 -7 -2 0 7 1 -4 8 0 -4 4 -6 -2 5 0 2 9 -4 -8 0 -8 7 4 -7 2 3 3 4 1 -1 7 -4 -2 6 0 3 -5 -7 2 0 -9 7 0 7 3 -6 0 1 7 6 2 2 -9 1 8 3 -3 2 -9 4 2 4 -5 6 0 -3 6 7 3 0 8 0 -4 7 0 -5 8 5 -5 -5 -1 0 9 -4 -3 -9 -1 7 -2 -7 -2 4 0 -6 6 -3 4 6 7 2 5 -8 -5 0 5 4 0 0 -4 0 -6 -5 3 -5 ...
output:
2.3323807579 2.3584952830 6.3245553203 2.2360679775 4.4721359550 2.2360679775 3.0103986447 2.8284271247 2.0275875101 2.1886350671 2.3035022138 8.2462112512 3.8873012632 2.0000000000 2.8284271247 3.7735924528 6.3245553203 14.1421356237 2.1081851068 4.0311288741 2.8284271247 inf 2.8284271247 7.2801098...
result:
wrong answer 1st numbers differ - expected: '2.1549170', found: '2.3323808', error = '0.0823529'