QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#88501 | #5570. Epidemic Escape | 5ab | RE | 3ms | 6180kb | C++17 | 5.6kb | 2023-03-16 12:57:45 | 2023-03-16 12:57:47 |
Judging History
answer
/* name: 5570
* author: 5ab
* created at: 2023-03-13
*/
#include <iostream>
#include <algorithm>
#include <iterator>
#include <iomanip>
#include <utility>
#include <cassert>
#include <vector>
#include <limits>
#include <tuple>
#include <cmath>
using namespace std;
typedef long long ll;
using db = long double;
const int max_n = 100000, max_q = 100000, max_k = 5;
inline ll sqr(int x) { return 1ll * x * x; }
struct point
{
int x, y; ll dis;
point(int _x = 0, int _y = 0) : x(_x), y(_y), dis(sqr(x) + sqr(y)) { }
point operator-(const point& rhs) const {
return point(x - rhs.x, y - rhs.y);
}
bool operator==(const point& rhs) {
return x == rhs.x && y == rhs.y;
}
};
vector<point> a, b;
vector<vector<point>> hul;
int ck[max_q];
vector<tuple<point, int, ll>> qr;
vector<db> cand[max_q];
inline ll dot(const point& lhs, const point& rhs) { return 1ll * lhs.x * rhs.x + 1ll * lhs.y * rhs.y; }
inline ll cross(const point& lhs, const point& rhs) { return 1ll * lhs.x * rhs.y - 1ll * rhs.x * lhs.y; }
db inters(const point& ln, const point& dr)
{
if (dot(ln, dr) <= 0)
return numeric_limits<db>::infinity();
db coef[2][3] = {
{ 2. * ln.x, 2. * ln.y, 1. * ln.dis },
{ 1. * dr.y, -1. * dr.x, 0. }
};
if (coef[0][0] == 0)
swap(coef[0], coef[1]);
db rto = coef[1][0] / coef[0][0];
for (int i = 0; i < 3; i++)
coef[1][i] -= rto * coef[0][i];
rto = coef[0][1] / coef[1][1];
for (int i = 0; i < 3; i++)
coef[0][i] -= rto * coef[1][i];
// cerr << coef[0][2] / coef[0][0] << " " << coef[1][2] / coef[1][1] << endl;
return hypot(coef[0][2] / coef[0][0], coef[1][2] / coef[1][1]);
}
signed main()
{
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
int n, q, stv = 0;
cin >> n;
a.reserve(n);
for (int i = 0, x, y; i < n; i++)
{
cin >> x >> y;
if (x == 0 && y == 0)
stv++;
else
a.emplace_back(x, y);
}
int sz = a.size();
assert(unique(a.begin(), a.end()) - a.begin() == sz);
for (int _ = 0; _ < max_k; _++)
{
// cerr << _ << " " << a.size() << endl;
hul.emplace_back();
hul[_].reserve(a.size());
vector<point>& stk = hul[_];
auto it = min_element(a.begin(), a.end(), [](auto lhs, auto rhs) {
return lhs.dis < rhs.dis;
});
auto stp = *it;
swap(*it, *a.begin());
stk.push_back(stp);
vector<tuple<point, ll>> tmp(a.size() - 1);
transform(a.begin() + 1, a.end(), tmp.begin(), [&](auto x) {
return make_tuple(x, cross(stp, x));
});
sort(tmp.begin(), tmp.end(), [](auto& lhs, auto& rhs) {
return ((get<1>(lhs) >= 0) ^ (get<1>(rhs) >= 0)) ?
get<1>(lhs) > get<1>(rhs) : cross(get<0>(lhs), get<0>(rhs)) > 0;
});
auto check = [&](point& lp, point& mp, point& rp) {
return cross(lp, rp) > 0 &&
__int128(cross(lp, rp)) * dot(rp - mp, lp - mp) +
__int128(dot(lp, rp)) * cross(rp - mp, lp - mp) >= 0;
};
for (auto& _$ : tmp)
{
auto& pt = get<0>(_$);
// cerr << pt.x << " " << pt.y << " " << get<1>(_$) << endl;
while (stk.size() > 1)
{
if (cross(stk.back(), pt) == 0 && dot(pt, stk.back()) > 0 && pt.dis < stk.back().dis)
{
b.push_back(stk.back());
stk.pop_back();
}
else if (check(end(stk)[-2], stk.back(), pt))
{
b.push_back(stk.back());
stk.pop_back();
}
else
break;
}
if (cross(stk.back(), pt) == 0 && dot(pt, stk.back()) > 0 && pt.dis >= stk.back().dis)
b.push_back(pt);
else if (check(stk.back(), pt, stk.front()))
b.push_back(pt);
else
stk.push_back(pt);
}
a.swap(b);
if (a.empty())
break;
b.clear();
}
/*
for (auto& x : hul)
{
for (auto& y : x)
cerr << "(" << y.x << "," << y.y << ") ";
cerr << endl;
}
*/
cin >> q;
qr.reserve(q);
for (int i = 0; i < q; i++)
{
int x, y;
cin >> x >> y >> ck[i];
if (x != 0 || y != 0)
qr.emplace_back(point(x, y), i, -1);
}
for (int _ = 0; _ < max_k && _ < int(hul.size()); _++)
{
auto& stk = hul[_];
int cs = stk.size();
for (auto& x : qr)
get<2>(x) = cross(stk.front(), get<0>(x));
sort(qr.begin(), qr.end(), [](auto& lhs, auto& rhs) {
return ((get<2>(lhs) >= 0) ^ (get<2>(rhs) >= 0)) ?
get<2>(lhs) > get<2>(rhs) : cross(get<0>(rhs), get<0>(lhs)) < 0;
});
for (int i = 0, j = 0; i < int(qr.size()); i++)
{
auto [pt, id, _$] = qr[i];
// cerr << pt.x << "," << pt.y << endl;
while (dot(stk[j], pt) <= 0 && cross(stk[j], stk[(j + 1) % cs]) > 0)
j = (j + 1) % cs;
while (inters(stk[j], pt) > inters(stk[(j + 1) % cs], pt))
j = (j + 1) % cs;
// cerr << stk[j].x << " " << stk[j].y << " " << pt.x << " " << pt.y << endl;
if (cs < (ck[id] - _) * 2)
{
for (int l = 0; l < cs; l++)
cand[id].push_back(inters(stk[l], pt));
}
else if (ck[id] - _ > 0)
{
for (int tc = 0, aj = j, bj = (j + 1) % cs; tc < ck[id] - _; tc++, aj--, bj++)
{
if (aj < 0) aj += cs;
if (bj == cs) bj = 0;
// cerr << aj << " " << bj << " ";
cand[id].push_back(inters(stk[aj], pt));
cand[id].push_back(inters(stk[bj], pt));
}
// cerr << " ---> " << cs << endl;
}
}
}
cout << fixed;
for (int i = 0; i < q; i++)
{
sort(cand[i].begin(), cand[i].end());
// for (auto x : cand[i])
// cerr << x << " ";
// cerr << endl;
if (ck[i] <= stv)
cout << "0.0000000000";
else if (int(cand[i].size()) < ck[i] - stv || cand[i][ck[i] - stv - 1] == numeric_limits<db>::infinity())
cout << "-1";
else
cout << setprecision(10) << cand[i][ck[i] - stv - 1];
cout << "\n";
}
return 0;
}
// started coding at: 03-13 11:17:16
详细
Test #1:
score: 100
Accepted
time: 1ms
memory: 6180kb
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: 3ms
memory: 6020kb
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: 3ms
memory: 6092kb
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: 6108kb
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
Dangerous Syscalls
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 ...