QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#55299 | #1343. Zombie Land | ckiseki | WA | 0ms | 3568kb | C++ | 5.7kb | 2022-10-13 01:50:39 | 2022-10-13 01:50:40 |
Judging History
answer
#pragma GCC optimize("Ofast")
#include <bits/stdc++.h>
using namespace std;
const long double eps = 1e-10;
// using PT = complex<int64_t>;
using lld = int64_t;
struct PT {
int64_t x, y;
PT(int64_t t_x, int64_t t_y) : x(t_x), y(t_y) {}
};
static constexpr lld real(PT &p) {
return p.x;
}
static constexpr lld imag(PT &p) {
return p.y;
}
static PT operator-(const PT &a, const PT &b) {
return {a.x - b.x, a.y - b.y};
}
int sgn(lld x) {
return (x > 0) - (x < 0);
}
lld cross(PT a, PT b) {
return a.x * b.y - a.y * b.x;
// 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) {
if (n == 1)
return 0;
int a, b, c;
int upA, dnC;
if (below(P, V[1], V[0]) && !above(P, V[n-1], V[0]))
return 0;
int cnt = 0;
for (a = 0, b = n;;) {
c = (a + b) / 2;
if (c == b || c == a) if (++cnt >= 3) assert (false);
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;
}
}
}
assert (false);
}
int Ltan(PT P, int n, PT *V) {
if (n == 1)
return 0;
int a, b, c;
int dnA, dnC;
if (above(P, V[n - 1], V[0]) && !below(P, V[1], V[0]))
return 0;
int cnt = 0;
for (a = 0, b = n;;) {
c = (a + b) / 2;
dnC = below(P, V[c + 1], V[c]);
if (c == b || c == a) if (++cnt >= 3) assert (false);
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;
}
}
}
assert (false);
}
void build(vector<PT> &dots) {
if (dots.size() <= 1) return;
sort(dots.begin(), dots.end(), [](PT a, PT b) {
if (real(a) != real(b)) return real(a) < real(b);
return imag(a) < 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() {
// freopen("i.in", "r", stdin);
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 " << v << ' ' << x << endl;
} else if (x > xz) {
R.emplace_back(x, v, i);
// cerr << "R " << v << ' ' << x << 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());
cout << cv.size() << endl;
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());
cout << cv.size() << endl;
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;
}
}
}
return 0;
cout << fixed << setprecision(15);
for (int i = 0; i < n; i++) {
if (ans[i] < -eps) {
cout << -1 << '\n';
} else {
cout << ans[i] << '\n';
}
}
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 0
Wrong Answer
time: 0ms
memory: 3568kb
input:
6 3 1 -5 0 5 0 -4 -3 0 -2 6 -3 2 -1
output:
6 4
result:
wrong answer 1st numbers differ - expected: '3.6666667', found: '6.0000000', error = '0.6363636'