QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#82204 | #5570. Epidemic Escape | heno239 | WA | 22ms | 14216kb | C++17 | 13.6kb | 2023-02-27 10:57:35 | 2023-02-27 10:57:36 |
Judging History
answer
#pragma GCC optimize("O3")
#pragma GCC optimize("unroll-loops")
#include<iostream>
#include<string>
#include<cstdio>
#include<vector>
#include<cmath>
#include<algorithm>
#include<functional>
#include<iomanip>
#include<queue>
#include<ciso646>
#include<random>
#include<map>
#include<set>
#include<bitset>
#include<stack>
#include<unordered_map>
#include<unordered_set>
#include<utility>
#include<cassert>
#include<complex>
#include<numeric>
#include<array>
#include<chrono>
using namespace std;
//#define int long long
typedef long long ll;
typedef unsigned long long ul;
typedef unsigned int ui;
//ll mod = 1;
constexpr ll mod = 998244353;
//constexpr ll mod = 1000000007;
const ll INF = mod * mod;
typedef pair<int, int>P;
#define rep(i,n) for(int i=0;i<n;i++)
#define per(i,n) for(int i=n-1;i>=0;i--)
#define Rep(i,sta,n) for(int i=sta;i<n;i++)
#define rep1(i,n) for(int i=1;i<=n;i++)
#define per1(i,n) for(int i=n;i>=1;i--)
#define Rep1(i,sta,n) for(int i=sta;i<=n;i++)
#define all(v) (v).begin(),(v).end()
typedef pair<ll, ll> LP;
template<typename T>
void chmin(T& a, T b) {
a = min(a, b);
}
template<typename T>
void chmax(T& a, T b) {
a = max(a, b);
}
template<typename T>
vector<T> vmerge(vector<T>& a, vector<T>& b) {
vector<T> res;
int ida = 0, idb = 0;
while (ida < a.size() || idb < b.size()) {
if (idb == b.size()) {
res.push_back(a[ida]); ida++;
}
else if (ida == a.size()) {
res.push_back(b[idb]); idb++;
}
else {
if (a[ida] < b[idb]) {
res.push_back(a[ida]); ida++;
}
else {
res.push_back(b[idb]); idb++;
}
}
}
return res;
}
template<typename T>
void cinarray(vector<T>& v) {
rep(i, v.size())cin >> v[i];
}
template<typename T>
void coutarray(vector<T>& v) {
rep(i, v.size()) {
if (i > 0)cout << " "; cout << v[i];
}
cout << "\n";
}
ll mod_pow(ll x, ll n, ll m = mod) {
if (n < 0) {
ll res = mod_pow(x, -n, m);
return mod_pow(res, m - 2, m);
}
if (abs(x) >= m)x %= m;
if (x < 0)x += m;
//if (x == 0)return 0;
ll res = 1;
while (n) {
if (n & 1)res = res * x % m;
x = x * x % m; n >>= 1;
}
return res;
}
//mod should be <2^31
struct modint {
int n;
modint() :n(0) { ; }
modint(ll m) {
if (m < 0 || mod <= m) {
m %= mod; if (m < 0)m += mod;
}
n = m;
}
operator int() { return n; }
};
bool operator==(modint a, modint b) { return a.n == b.n; }
bool operator<(modint a, modint b) { return a.n < b.n; }
modint operator+=(modint& a, modint b) { a.n += b.n; if (a.n >= mod)a.n -= (int)mod; return a; }
modint operator-=(modint& a, modint b) { a.n -= b.n; if (a.n < 0)a.n += (int)mod; return a; }
modint operator*=(modint& a, modint b) { a.n = ((ll)a.n * b.n) % mod; return a; }
modint operator+(modint a, modint b) { return a += b; }
modint operator-(modint a, modint b) { return a -= b; }
modint operator*(modint a, modint b) { return a *= b; }
modint operator^(modint a, ll n) {
if (n == 0)return modint(1);
modint res = (a * a) ^ (n / 2);
if (n % 2)res = res * a;
return res;
}
ll inv(ll a, ll p) {
return (a == 1 ? 1 : (1 - p * inv(p % a, a)) / a + p);
}
modint operator/(modint a, modint b) { return a * modint(inv(b, mod)); }
modint operator/=(modint& a, modint b) { a = a / b; return a; }
const int max_n = 1 << 20;
modint fact[max_n], factinv[max_n];
void init_f() {
fact[0] = modint(1);
for (int i = 0; i < max_n - 1; i++) {
fact[i + 1] = fact[i] * modint(i + 1);
}
factinv[max_n - 1] = modint(1) / fact[max_n - 1];
for (int i = max_n - 2; i >= 0; i--) {
factinv[i] = factinv[i + 1] * modint(i + 1);
}
}
modint comb(int a, int b) {
if (a < 0 || b < 0 || a < b)return 0;
return fact[a] * factinv[b] * factinv[a - b];
}
modint combP(int a, int b) {
if (a < 0 || b < 0 || a < b)return 0;
return fact[a] * factinv[a - b];
}
ll gcd(ll a, ll b) {
a = abs(a); b = abs(b);
if (a < b)swap(a, b);
while (b) {
ll r = a % b; a = b; b = r;
}
return a;
}
using ld = long double;
//typedef long double ld;
typedef pair<ld, ld> LDP;
const ld eps = 1e-6;
const ld pi = acosl(-1.0);
template<typename T>
void addv(vector<T>& v, int loc, T val) {
if (loc >= v.size())v.resize(loc + 1, 0);
v[loc] += val;
}
/*const int mn = 2000005;
bool isp[mn];
vector<int> ps;
void init() {
fill(isp + 2, isp + mn, true);
for (int i = 2; i < mn; i++) {
if (!isp[i])continue;
ps.push_back(i);
for (int j = 2 * i; j < mn; j += i) {
isp[j] = false;
}
}
}*/
//[,val)
template<typename T>
auto prev_itr(set<T>& st, T val) {
auto res = st.lower_bound(val);
if (res == st.begin())return st.end();
res--; return res;
}
//[val,)
template<typename T>
auto next_itr(set<T>& st, T val) {
auto res = st.lower_bound(val);
return res;
}
using mP = pair<modint, modint>;
mP operator+(mP a, mP b) {
return { a.first + b.first,a.second + b.second };
}
mP operator+=(mP& a, mP b) {
a = a + b; return a;
}
mP operator-(mP a, mP b) {
return { a.first - b.first,a.second - b.second };
}
mP operator-=(mP& a, mP b) {
a = a - b; return a;
}
LP operator+(LP a, LP b) {
return { a.first + b.first,a.second + b.second };
}
LP operator+=(LP& a, LP b) {
a = a + b; return a;
}
LP operator-(LP a, LP b) {
return { a.first - b.first,a.second - b.second };
}
LP operator-=(LP& a, LP b) {
a = a - b; return a;
}
mt19937 mt(time(0));
const string drul = "DRUL";
string senw = "SENW";
//DRUL,or SENW
int dx[4] = { 1,0,-1,0 };
int dy[4] = { 0,1,0,-1 };
//-----------------------------------------
typedef complex<ld> Point;
ld dot(Point a, Point b) { return real(conj(a) * b); }
ld cross(Point a, Point b) { return imag(conj(a) * b); }
namespace std {
bool operator<(const Point& lhs, const Point& rhs) {
return lhs.real() == rhs.real() ? lhs.imag() < rhs.imag() : lhs.real() < rhs.real();
}
}
struct Line {
Point a, b;
};
struct Circle {
Point p; ld r;
};
int ccw(Point a, Point b, Point c) {
b -= a; c -= a;
if (cross(b, c) > eps)return 1;//counter clockwise
if (cross(b, c) < -eps)return -1;//clock wise
if (dot(b, c) < 0)return 2;//c--a--b on line
if (norm(b) < norm(c))return -2;//a--b--c on line
return 0; //a--c--b on line
}
bool eq(ld a, ld b) {
return abs(a - b) < eps;
}
//2直線の交差判定
bool isis_ll(Line l, Line m) {
return !eq(cross(l.b - l.a, m.b - m.a), 0);
}
//直線と線分の交差判定
bool isis_ls(Line l, Line s) {
return (cross(l.b - l.a, s.a - l.a) * cross(l.b - l.a, s.b - l.a) < eps);
}
//点が直線上に存在するか
bool isis_lp(Line l, Point p) {
return (abs(cross(l.b - p, l.a - p)) < eps);
}
//点が線分上に存在するか
bool isis_sp(Line s, Point p) {
//誤差がisis_lpに比べて大きいので、できるだけisis_lpを使う
return (abs(s.a - p) + abs(s.b - p) - abs(s.b - s.a) < eps);
}
//線分と線分の交差判定
//bool isis_ss(Line s, Line t) {
// return(cross(s.b - s.a, t.a - s.a)*cross(s.b - s.a, t.b - s.a) < -eps && cross(t.b - t.a, s.a - t.a)*cross(t.b - t.a, s.b - t.a) < -eps);
//}
//線分と線分の交差判定2
//本当にそれは線分ですか?(check {(0,0),(2,0)},{(1,0),(1,0)})
bool isis_ss(Line s, Line t) {
return ccw(s.a, s.b, t.a) * ccw(s.a, s.b, t.b) <= 0 && ccw(t.a, t.b, s.a) * ccw(t.a, t.b, s.b) <= 0;
}
//点から直線への垂線の足
Point proj(Line l, Point p) {
ld t = dot(p - l.a, l.a - l.b) / norm(l.a - l.b);
return l.a + t * (l.a - l.b);
}
//直線と直線の交点
//平行な2直線に対しては使うな!!!!
Point is_ll(Line s, Line t) {
Point sv = s.b - s.a; Point tv = t.b - t.a;
return s.a + sv * cross(tv, t.a - s.a) / cross(tv, sv);
}
void solve() {
int n; cin >> n;
vector<LP> p(n);
int c0 = 0;
rep(i, n) {
int x, y; cin >> x >> y;
x *= 2; y *= 2;
p[i] = { x,y };
if (x == 0 && y == 0) {
c0++;
}
}
auto calcd = [&](int i) {
ll res = (ll)p[i].first * p[i].first + (ll)p[i].second * p[i].second;
return res;
};
auto issamedir = [&](int i, int j) {
ll z = (ll)p[i].first * p[j].second - (ll)p[j].first * p[i].second;
ll d = (ll)p[i].first * p[j].first + (ll)p[i].second * p[j].second;
if (z == 0 && d > 0)return true;
else return false;
};
vector<Point> vp(n);
rep(i, n)vp[i] = { (ld)p[i].first,(ld)p[i].second };
vector<Line> lp(n);
rep(i, n) {
if (p[i] == LP{ 0,0 })continue;
int x = p[i].first, y = p[i].second;
lp[i].a = { (ld)x,(ld)y };
lp[i].b = { (ld)(x - y),(ld)(y + x) };
}
vector<ld> pt(n);
rep(i, n) {
if (p[i] == LP{ 0,0 })continue;
pt[i] = atan2(p[i].second, p[i].first);
}
auto comp = [&](int i, int j) {
return pt[i] < pt[j];
};
vector<int> ids;
rep(i, n) {
if (p[i] == LP{ 0,0 })continue;
ids.push_back(i);
}
auto check = [&](int i, int j, int k) {
if (ccw(vp[i], { 0,0 }, vp[j]) != -1)return true;
Point pm = is_ll(lp[i], lp[k]);
if (ccw(lp[j].a, lp[j].b, pm) == -1)return true;
else return false;
};
sort(all(ids), comp);
vector<vector<int>> vs;
rep(_, 5) {
if (ids.empty())continue;
ll mi = INF;
int ci = -1;
rep(i, ids.size()) {
int id = ids[i];
ll dx = p[id].first;
ll dy = p[id].second;
ll d = dx * dx + dy * dy;
if (d < mi) {
mi = d;
ci = i;
}
}
vector<int> nids;
Rep(i, ci, ids.size()) {
int id = ids[i];
if (nids.size() && issamedir(nids.back(), id)) {
if (calcd(nids.back()) <= calcd(id)) {
continue;
}
else{
nids.pop_back();
}
}
while (nids.size() >= 2 && !check(nids[nids.size() - 2], nids[nids.size() - 1], id)) {
nids.pop_back();
}
nids.push_back(id);
}
rep(i, ci + 1) {
int id = ids[i];
if (nids.size() && issamedir(nids.back(), id)) {
if (calcd(nids.back()) <= calcd(id)) {
continue;
}
else {
nids.pop_back();
}
}
while (nids.size() >= 2 && !check(nids[nids.size() - 2], nids[nids.size() - 1], id)) {
nids.pop_back();
}
nids.push_back(id);
}
if (nids.size() > 1) {
assert(nids.back() == ids[ci]);
nids.pop_back();
}
vs.push_back(nids);
vector<bool> used(n);
for (int id : nids)used[id] = true;
nids.clear();
for (int id : ids) {
if (!used[id])nids.push_back(id);
}
swap(ids, nids);
}
vector<int> locs(vs.size());
rep(i, vs.size()) {
ld mi = INF;
int cj = -1;
rep(j, vs[i].size()) {
ld val = pt[vs[i][j]];
if (p[vs[i][j]].first <= 0 && p[vs[i][j]].second >= 0) {
//cout << "eeeee "<<val<<"\n";
val -= 4 * pi;
//cout << "eeeee " << val << "\n";
}
if (val < mi) {
mi = pt[vs[i][j]];
//mi = val;
cj = j;
}
}
//cout << "!? " << cj << "\n";
rep(j, cj)vs[i].push_back(vs[i][j]);
vs[i].erase(vs[i].begin(), vs[i].begin() + cj);
/*cout << "nhello\n";
rep(j, vs[i].size()) {
cout << pt[vs[i][j]] << " ";
}cout << "\n";*/
}
/*rep(i, vs.size()) {
cout << "hello\n";
coutarray(vs[i]);
}*/
int q; cin >> q;
vector<ld> ans(q, -1);
vector<LP> qp(q);
vector<Point> vq(q);
vector<int> qk(q);
rep(i, q) {
int x, y; cin >> x >> y;
x *= 2; y *= 2;
qp[i] = { x,y };
vq[i] = { (ld)x,(ld)y };
cin >> qk[i];
}
vector<ld> qt(q);
rep(i, q) {
if (qp[i] == LP{ 0,0 })continue;
ld t = atan2(qp[i].second, qp[i].first);
qt[i] = t;
}
auto compq = [&](int i, int j) {
return qt[i] < qt[j];
};
vector<int> idq;
rep(i, q) {
if (qp[i] == LP{ 0,0 })continue;
idq.push_back(i);
}
sort(all(idq), compq);
//query,input
auto calc = [&](int i, int j)->ld {
ll a = (ll)p[j].first * p[j].first + (ll)p[j].second * p[j].second;
ll b = (ll)p[j].first * qp[i].first + (ll)p[j].second * qp[i].second;
if (b <= 0)return -1;
//cout << "? " << i << " " << j << " " << a << " " << b << "\n";
b *= 2;
return a / (ld)b;
};
rep(i, idq.size()) {
int id = idq[i];
//cout << "ee "<<qt[id] << "\n";
int k = qk[id]; k--;
vector<ld> vals;
rep(j, vs.size()) {
while (true) {
int id0 = vs[j][locs[j]];
int id1 = vs[j][(locs[j] + 1) % vs[j].size()];
ld v0 = calc(id, id0);
ld v1 = calc(id, id1);
if (v0 < 0 && v1 < 0) {
locs[j]++; locs[j] %= vs[j].size();
if (ccw(vp[id0], vp[id1], Point{ 0,0 }) != 1) {
break;
}
}
else if (v0 < 0) {
locs[j]++; locs[j] %= vs[j].size();
}
else if (v1 < 0) {
break;
}
else {
if (v0 > v1) {
locs[j]++; locs[j] %= vs[j].size();
}
else {
break;
}
}
}
int len = min((int)vs[j].size(), 2 * k + 1);
int le = locs[j] - k;
le %= (int)vs[j].size(); if (le < 0)le += (int)vs[j].size();
rep(x, len) {
int loc = (le + x) % vs[j].size();
ld val = calc(id, vs[j][loc]);
//cout << "? " << id << " " <<vs[j][loc]<<" "<< val << "\n";
if (val > 0)vals.push_back(val);
}
}
sort(all(vals));
//cout << "! " << vals.size() << "\n";
if (vals.size() <= k) {
ans[id] = -1;
}
else {
ld r = sqrt((ll)qp[id].first * qp[id].first + (ll)qp[id].second * qp[id].second);
ans[id] = vals[k] * r / 2;
}
}
/*rep(i, q) {
vector<ld> vals;
ld r = sqrt((ll)qp[i].first * qp[i].first + (ll)qp[i].second * qp[i].second);
rep(j, n) {
ld val = calc(i, j);
val = val * r / 2;
vals.push_back(val);
}
sort(all(vals));
if (i == 8) {
coutarray(vals);
}
}*/
rep(i, q) {
if (ans[i] < 0)cout << -1 << "\n";
else cout << ans[i] << "\n";
}
}
signed main() {
ios::sync_with_stdio(false);
cin.tie(0);
cout << fixed << setprecision(10);
//init_f();
//init();
//while(true)
//expr();
//int t; cin >> t; rep(i, t)
solve();
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 7ms
memory: 12092kb
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: 12140kb
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: 12144kb
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: 8ms
memory: 12212kb
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: 22ms
memory: 14216kb
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:
wrong answer 89th numbers differ - expected: '2.0487877', found: '2.0622665', error = '0.0065789'