QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#55288 | #1343. Zombie Land | ckiseki | WA | 2ms | 3920kb | C++ | 4.9kb | 2022-10-12 22:53:17 | 2022-10-12 22:53:18 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
const long double eps = 1e-10;
using PT = complex<int64_t>;
using lld = int64_t;
int sgn(lld x) {
return (x > 0) - (x < 0);
}
lld cross(PT a, PT b) {
return imag(conj(a) * b);
}
int ori(PT a, PT b, PT c) {
return sgn(cross(b - a, c - a));
}
#define above(P, Vi, Vj) (ori(P, Vi, Vj) > 0)
#define below(P, Vi, Vj) (ori(P, Vi, Vj) < 0)
int Rtan(PT P, int n, PT *V) {
int a, b, c;
int upA, dnC;
if (below(P, V[1], V[0]) && !above(P, V[n-1], V[0]))
return 0;
for (a = 0, b = n;;) {
c = (a + b) / 2;
dnC = below(P, V[c+1], V[c]);
if (dnC && !above(P, V[c-1], V[c]))
return c;
upA = above(P, V[a+1], V[a]);
if (upA) {
if (dnC) {
b = c;
} else {
if (above(P, V[a], V[c]))
b = c;
else
a = c;
}
} else {
if (!dnC) {
a = c;
} else {
if (below(P, V[a], V[c]))
b = c;
else
a = c;
}
}
}
}
int Ltan(PT P, int n, PT *V) {
int a, b, c;
int dnA, dnC;
if (above(P, V[n - 1], V[0]) && !below(P, V[1], V[0]))
return 0;
for (a = 0, b = n;;) {
c = (a + b) / 2;
dnC = below(P, V[c + 1], V[c]);
if (above(P, V[c - 1], V[c]) && !dnC)
return c;
dnA = below(P, V[a + 1], V[a]);
if (dnA) {
if (!dnC) {
b = c;
} else {
if (below(P, V[a], V[c]))
b = c;
else
a = c;
}
} else {
if (dnC) {
a = c;
} else {
if (above(P, V[a], V[c]))
b = c;
else
a = c;
}
}
}
}
#define MP make_pair
void build(vector<PT> &dots) {
sort(dots.begin(), dots.end(), [](PT a, PT b) {
return MP(real(a), imag(a)) < MP(real(b), imag(b));
});
vector<PT> ans(1, dots[0]);
for (int ct = 0; ct < 2; ++ct, reverse(dots.begin(), dots.end())) {
for (int i = 1, t = ans.size(); i < dots.size(); i++) {
while (ans.size() > t && ori(
ans[ans.size() - 2], ans.back(), dots[i]) <= 0)
ans.pop_back();
ans.emplace_back(dots[i]);
}
ans.pop_back(), ans.swap(dots);
}
}
long double slope(PT a, PT b) {
if (real(a) == real(b)) {
return -1e9;
} else {
return -(imag(a) - imag(b)) / (long double)(real(a) - real(b));
}
}
int main() {
cin.tie(nullptr)->sync_with_stdio(false);
int n;
cin >> n;
int xz, vz;
cin >> xz >> vz;
vector<tuple<int,int,int>> L, R;
for (int i = 0; i < n; i++) {
int x, v;
cin >> x >> v;
v -= vz;
if (x < xz) {
L.emplace_back(x, v, i);
// cerr << "L " << x << ' ' << v << endl;
} else if (x > xz) {
R.emplace_back(x, v, i);
// cerr << "R " << x << ' ' << v << endl;
} else
__builtin_unreachable();
}
// cerr << fixed << setprecision(3);
vector<long double> ans(n, -1);
{
vector<PT> cv;
for (auto [x, v, id]: L) {
cv.emplace_back(v, x);
}
cv.emplace_back(0, xz);
// build(cv);
cv.emplace_back(cv.front());
for (auto [x, v, id]: R) {
// for (int j = 0; j < cv.size(); j++) {
for (int j: {
Ltan({v, x}, cv.size()-1, cv.data()),
Rtan({v, x}, cv.size()-1, cv.data())
}) {
long double s = slope({v,x}, cv[j]);
if (s < 0) continue;
if (ans[id] < -eps || ans[id] > s)
ans[id] = s;
}
}
}
{
vector<PT> cv;
for (auto [x, v, id]: R) {
cv.emplace_back(v, x);
}
cv.emplace_back(0, xz);
// build(cv);
cv.emplace_back(cv.front());
for (auto [x, v, id]: L) {
// for (int j = 0; j < cv.size(); j++) {
for (int j: {
Ltan({v, x}, cv.size()-1, cv.data()),
Rtan({v, x}, cv.size()-1, cv.data())
}) {
long double s = slope({v,x}, cv[j]);
if (s < 0) continue;
if (ans[id] < -eps || ans[id] > s)
ans[id] = s;
}
}
}
cout << fixed << setprecision(15);
for (int i = 0; i < n; i++) {
if (ans[i] < -eps) {
cout << -1 << '\n';
} else {
cout << ans[i] << '\n';
}
}
}
详细
Test #1:
score: 100
Accepted
time: 2ms
memory: 3764kb
input:
6 3 1 -5 0 5 0 -4 -3 0 -2 6 -3 2 -1
output:
3.666666666666667 2.000000000000000 -1 6.000000000000000 0.750000000000000 2.000000000000000
result:
ok 6 numbers
Test #2:
score: 0
Accepted
time: 2ms
memory: 3816kb
input:
5 31415 -926 5358 979 323846 26 -433832 7950 288 -4 -1971 -69
output:
13.678215223097113 95.618122160524987 52.416291122127084 33.760303687635575 38.956826137689615
result:
ok 5 numbers
Test #3:
score: -100
Wrong Answer
time: 1ms
memory: 3920kb
input:
972 98740224 301565350 897445571 19067267 -528259301 772813962 88724382 432443246 668138287 561147750 -111697007 795680328 716395194 388109596 -289144978 72929322 -935429651 690324478 632898250 -359347321 -388094843 -753263424 416481084 91553128 460683861 290773570 445572029 -788653120 -239712630 23...
output:
1.891490710947661 2.240893597101047 3.495350335602818 5.652284210575848 1.265131341112392 3.235353182864579 22.030175955967517 3.823549717935804 1.025611428720796 -1 4.347347349179602 2.051577374868619 0.623664335435539 5.292181684594715 0.871977004104281 -1 -1 3.181994956147331 3.372933703270793 3....
result:
wrong answer 1st numbers differ - expected: '0.8555381', found: '1.8914907', error = '1.0359527'