QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#338386 | #5570. Epidemic Escape | ucup-team1198 | WA | 1044ms | 29312kb | C++20 | 8.1kb | 2024-02-25 21:11:19 | 2024-02-25 21:11:20 |
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 = long double;
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-16;
const int MAXK = 20;
vector<Vector> convex(vector<Vector>& p) {
if (p.empty()) return p;
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;
});
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;
}
int norm(int x, int n) {
while (x >= n) x -= n;
return x;
}
int reduce(int x, int n) {
while (x < 0) x += n;
return x;
}
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 = norm((i + (1 << k)), n);
int i2 = reduce((i - (1 << k)), 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 = norm((i + 1) , n);
int t2 = reduce((i - 1) , n);
for (int _ = 0; _ < sz; ++_) {
if (dir * p[t1] > dir * p[t2]) {
ans.push_back(p[t1]);
t1 = norm((t1 + 1), n);
} else {
ans.push_back(p[t2]);
t2 = reduce((t2 - 1) , 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 + MAXK - 5; ++i) {
auto res = get_bst(dir, hulls[i], k - i + MAXK - 5);
/**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: 0ms
memory: 4056kb
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: 1ms
memory: 3812kb
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: 1ms
memory: 3920kb
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: 3864kb
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: 0
Accepted
time: 92ms
memory: 5660kb
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.1549170046 2.1672659357 2.0676430855 2.1118419787 2.1118419787 2.1118419787 2.1249872786 2.1213203436 2.0275875101 2.0928822829 2.1415372144 2.0615528128 2.1549170046 2.0000000000 2.1213203436 2.1672659357 2.0676430855 2.0203050891 2.0676430855 2.1415372144 2.1213203436 2.0000000000 2.1213203436 2...
result:
ok 10000 numbers
Test #6:
score: 0
Accepted
time: 93ms
memory: 5720kb
input:
10000 -90174 318421 -37261 138897 -260388 -302590 -906833 35071 317743 -283220 390311 -85301 880987 325969 -315218 -116767 103089 -8223 -134988 -973121 -444593 229407 -552060 549321 265624 -337609 -264546 322379 28687 110143 467764 303005 -335748 32188 213125 274156 240105 751 -81255 -129323 148563 ...
output:
218.3023759373 481.6627119891 792.1850756018 579.9542618493 807.7094462678 242.5921754846 882.2675147667 530.7807802597 664.1821759610 796.3607397675 662.7071678987 639.0726192787 125.8211827153 745.7291752667 732.4967218100 676.5327801482 808.9964118683 427.9627407901 1298.3736892031 616.3789303001...
result:
ok 10000 numbers
Test #7:
score: 0
Accepted
time: 1044ms
memory: 29312kb
input:
100000 -14593321 17388753 13488647 1223793 33907737 -8731155 -14502324 73522129 -13933178 -13752140 9462275 13349398 14636622 31405249 5160247 -69775840 -49415260 -40092130 -9926862 -25806124 14982829 -8025116 -5492901 4568113 48872077 86636033 19374632 32538501 -16657133 -11624530 -15398598 -966935...
output:
1331.4977763324 1193.9602287451 1171.2427261871 1856.2890362990 2681.8829458540 1170.8707408363 1128.3614715722 1855.8783379892 3518.3241479702 1541.7860082154 1515.0151223165 1124.4065660466 2146.7167113138 1179.4306789471 1164.1588782715 1251.5110829082 2737.3506509053 1117.3515869945 2213.1263918...
result:
ok 100000 numbers
Test #8:
score: -100
Wrong Answer
time: 706ms
memory: 29080kb
input:
100000 -60674143 79489917 99210432 12541486 -99948887 -3196593 57015830 -82153478 10407645 99456921 -90320128 42921703 93983821 34161956 96773928 -25195355 69603194 71801068 27259746 -96212811 96031961 27890165 76618755 -64261689 -99095784 13417302 -95521354 -29591717 -34815155 -93743823 -93393132 -...
output:
52688057.7462448516 50252777.6339667084 50023117.8477325216 113032840.1191277413 50001065.7754694409 53857449.3110424285 57127881.0407733964 53730103.8182993231 259081451.5501204659 124747368.1718054871 50007250.7973509014 51019441.7224818776 50190950.1468887715 256853239.8591640663 61484125.5979333...
result:
wrong answer 1st numbers differ - expected: '49999995.0818662', found: '52688057.7462449', error = '0.0537613'