QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#87792 | #5570. Epidemic Escape | applese | TL | 259ms | 12700kb | C++14 | 7.0kb | 2023-03-14 10:41:29 | 2023-03-14 10:41:33 |
Judging History
answer
#include<bits/stdc++.h>
using namespace std;
const int maxn = 1e5 + 5;
const double eps = 1e-9;
int Dcmp(double x) {
return x < -eps ? -1 : x > eps ? 1 : 0;
}
struct Point {
double x, y;
int id;
Point(double x = 0, double y = 0, int id = 0) : x(x), y(y), id(id) {}
Point operator == (const Point &rhs) const {
return Dcmp(x - rhs.x) == 0 && Dcmp(y - rhs.y) == 0;
}
Point operator + (const Point &rhs) const {
return Point(x + rhs.x, y + rhs.y);
}
Point operator - (const Point &rhs) const {
return Point(x - rhs.x, y - rhs.y);
}
Point operator * (const double &k) const {
return Point(x * k, y * k);
}
Point operator / (const double &k) const {
return Point(x / k, y / k);
}
double operator * (const Point &rhs) const {
return x * rhs.x + y * rhs.y;
}
double operator ^ (const Point &rhs) const {
return x * rhs.y - y * rhs.x;
}
double len2() {
return x * x + y * y;
}
double len() {
return sqrt(len2());
}
Point Unit() {
return *this / len();
}
}p[maxn];
double invr = 2e4;
int n, cntp, tot, vis[maxn], q, sz[6], dismax[6], cnt[6];
vector<Point> hull[6], now;
int Left(Point a, Point b, Point c) { // b is left of ac
return Dcmp((b - a) ^ (c - a)) >= 0;
}
Point base;
vector<Point> Convex(vector<Point> a) {
int n = a.size(), cnt = 0;
if(n < 3)
return a;
for(auto p : a)
if(make_pair(p.x, p.y) < make_pair(base.x, base.y))
base = p;
sort(a.begin(), a.end(), [](const Point &a, const Point &b) {
int d = Dcmp((a - base) ^ (b - base));
if(d)
return d > 0;
return Dcmp((a - base).len2() - (b - base).len2()) < 0;
});
vector<Point> res;
for(int i = 0; i < n; ++ i) {
while(cnt > 1 && Left(res[cnt - 2], a[i], res[cnt - 1]))
-- cnt, res.pop_back();
res.push_back(a[i]), ++ cnt;
}
int fixed = cnt;
for(int i = n - 2; ~i; -- i) {
while(cnt > fixed && Left(res[cnt - 2], a[i], res[cnt - 1]))
-- cnt, res.pop_back();
res.push_back(a[i]), ++ cnt;
}
res.pop_back();
return res;
}
double Dis(Point s, Point t, Point p) {
Point v1 = t - s, v2 = p - s;
return (v2 ^ v1) / v1.len();
}
int lp[6], rp[6];
struct Node {
double dd;
int hullid, id;
Node(double dd = 0, int hullid = 0, int id = 0) : dd(dd), hullid(hullid), id(id) {}
bool operator < (const Node &rhs) const {
int d = Dcmp(dd - rhs.dd);
return d ? d < 0 : hullid == rhs.hullid ? id < rhs.id : hullid < rhs.hullid;
}
};
priority_queue<Node>que;
vector<Point> lower[6], upper[6];
pair<double, int> Get(vector<Point> con, Point p) {
int l = 0, r = (int)con.size() - 2;
for(; l + 1 < r; ) {
int mid = (l + r) / 2;
if(Dcmp((con[mid + 1] - con[mid]) ^ p) > 0)
r = mid;
else
l = mid;
}
return max(make_pair(p ^ con[r], r), make_pair(p ^ con[0], 0));
}
int Gett(int id, Point v) {
auto ret = Get(upper[id], v);
ret.second = (ret.second + (int)lower[id].size() - 1) % sz[id];
ret = max(ret, Get(lower[id], v));
return ret.second;
}
int main() {
scanf("%d", &n);
for(int i = 1, x, y; i <= n; ++ i) {
scanf("%d%d", &x, &y);
if(x == 0 && y == 0) {
++ cntp;
}
else {
Point w = Point(x, y, i);
Point v = w.Unit();
double nowl = w.len();
double newl = invr * invr / nowl;
p[++ tot] = v * newl;
p[tot].id = tot;
}
}
for(int k = 0; k < 5; ++ k) {
now.clear();
for(int i = 1; i <= tot; ++ i) {
if(!vis[i]) {
now.push_back(p[i]);
}
}
hull[k] = Convex(now);
sz[k] = hull[k].size();
if(sz[k]) {
// cerr << "Hull " << k << ": " << endl;
for(auto w : hull[k]) {
vis[w.id] = 1;
// cerr << "(" << w.x << ", " << w.y << ") Id = " << w.id << endl;
}
int pos = 0;
for(int i = 0; i < sz[k]; ++ i) {
if(Dcmp(hull[k][i].x - hull[k][pos].x) > 0) {
pos = i;
}
}
// cerr << pos << endl;
for(int i = 0; i <= pos; ++ i) {
lower[k].push_back(hull[k][i]);
}
for(int i = pos; i < sz[k]; ++ i) {
upper[k].push_back(hull[k][i]);
}
upper[k].push_back(hull[k][0]);
}
// cerr << sz[k] << endl;
}
scanf("%d", &q);
for(int x, y, k; q --; ) {
scanf("%d%d%d", &x, &y, &k);
if(!x && !y) {
puts("-1");
continue;
}
if(k <= cntp) {
puts("0");
continue;
}
k -= cntp;
while(!que.empty())
que.pop();
double newl = invr * invr * 4;
Point dir = Point(-y, x), v = Point(x, y).Unit();
Point now = v * newl, nowp = now + dir; // now + dir
for(int i = 0; i < 5; ++ i) {
if(!sz[i])
continue;
// fprintf(stderr, "Hull %d: \n", i);
// for(auto w : hull[i])
// fprintf(stderr, "Dis: %.15f Id: %d\n", Dis(now, nowp, w), w.id);
dismax[i] = cnt[i] = 0;
if(sz[i] > 1) {
// int pos1 = Gett(i, dir), pos2 = Gett(i, Point(-dir.x, -dir.y));
// dismax[i] = pos1;
// for(int C = 0, x = pos2; C <= 2; ++ C, x = (x + 1) % sz[i]) {
// if(Dcmp(Dis(now, nowp, hull[i][dismax[i]]) - Dis(now, nowp, hull[i][x])) < 0)
// dismax[i] = x;
// }
// for(int C = 0, x = pos1; C <= 2; ++ C, x = (x + 1) % sz[i]) {
// if(Dcmp(Dis(now, nowp, hull[i][dismax[i]]) - Dis(now, nowp, hull[i][x])) < 0)
// dismax[i] = x;
// }
// for(int C = 0, x = pos2; C <= 2; ++ C, x = (x + sz[i] - 1) % sz[i]) {
// if(Dcmp(Dis(now, nowp, hull[i][dismax[i]]) - Dis(now, nowp, hull[i][x])) < 0)
// dismax[i] = x;
// }
// for(int C = 0, x = pos1; C <= 2; ++ C, x = (x + sz[i] - 1) % sz[i]) {
// if(Dcmp(Dis(now, nowp, hull[i][dismax[i]]) - Dis(now, nowp, hull[i][x])) < 0)
// dismax[i] = x;
// }
// for(int j = 0; j < sz[i]; ++ j) {
// int d = Dcmp(Dis(now, nowp, hull[i][dismax[i]]) - Dis(now, nowp, hull[i][j]));
// if(d < 0) {
// assert(0);
// }
// }
for(int j = 0; j < sz[i]; ++ j) {
if(Dcmp(Dis(now, nowp, hull[i][dismax[i]]) - Dis(now, nowp, hull[i][j])) < 0)
dismax[i] = j;
}
}
// cerr << dismax[i] << endl;
lp[i] = rp[i] = dismax[i];
que.push(Node(Dis(now, nowp, hull[i][dismax[i]]), i, dismax[i]));
}
double ans = 1e18;
for(int c = 1; c <= k; ++ c) {
Node w = que.top();
que.pop();
// cerr << w.dd << " " << w.hullid << " " << w.id << " " << w.dd + newl << endl;
if(Dcmp(w.dd + newl) <= 0 || Dcmp(invr * invr / (w.dd + newl) / 2 - 1e9) > 0)
break;
if(c == k) {
ans = newl + w.dd;
break;
}
int i = w.hullid, pos = w.id;
++ cnt[i];
if(cnt[i] == sz[i])
continue;
if(lp[i] == pos) {
-- lp[i];
if(lp[i] < 0)
lp[i] += sz[i];
if(lp[i] != rp[i]) {
que.push(Node(Dis(now, nowp, hull[i][lp[i]]), i, lp[i]));
}
}
if(rp[i] == pos) {
++ rp[i];
if(rp[i] >= sz[i])
rp[i] -= sz[i];
if(lp[i] != rp[i]) {
que.push(Node(Dis(now, nowp, hull[i][rp[i]]), i, rp[i]));
}
}
}
// cerr << ans << endl;
if(ans > 1e16 || Dcmp(ans) <= 0 || Dcmp(invr * invr / ans / 2 - 1e9) > 0)
puts("-1");
else
// printf("%lld\n", (long long)round(invr * invr / ans / 2 * 1e7));
printf("%.15f\n", invr * invr / ans / 2);
}
}
詳細信息
Test #1:
score: 100
Accepted
time: 3ms
memory: 6072kb
input:
5 5 -3 5 4 -6 2 -5 0 4 1 2 -3 -10 1 6 -9 1
output:
8.700255424092052 3.226019562257246
result:
ok 2 numbers
Test #2:
score: 0
Accepted
time: 3ms
memory: 6024kb
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.167762968124700 26.162950903902797 5.461488320163356 6.363961030678952 -1 5.289408221642564 3.726779962499644 4.609772228646474 2.929442379201408 4.761728940206468
result:
ok 10 numbers
Test #3:
score: 0
Accepted
time: 0ms
memory: 5992kb
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.000000000000008 5.130527658008234 -1 -1 -1 3.535533905932721 2.236067977499784 11.985407794480672 15.320646925707983 3.535533905932721 2.462740091320331 4.527692569068690 3.762998305872593 15.320646925707983 2.981423969999723 5.621703504797920 7.071067811865501 2.735793833832261 -1 8.125000000000012
result:
ok 20 numbers
Test #4:
score: 0
Accepted
time: 3ms
memory: 6036kb
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.758678868756732 29.571405997862154 24.622144504490112 27.771745654731312 26.678366712895418 24.423702460471045 28.893348196396108 29.776169557759353 31.940362970517576 27.214901602376305 31.728095045749107 27.071160551680823 25.299110030617499 26.871065152125734 28.995839453428850 28.356314246198...
result:
ok 100 numbers
Test #5:
score: 0
Accepted
time: 21ms
memory: 6300kb
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.154917004616731 2.167265935742736 2.067643085494703 2.111841978749800 2.111841978749800 2.111841978749800 2.124987278610400 2.121320343559645 2.027587510099409 2.092882282881673 2.141537214391807 2.061552812808829 2.154917004616731 2.000000000000000 2.121320343559650 2.167265935742736 2.0676430854...
result:
ok 10000 numbers
Test #6:
score: 0
Accepted
time: 29ms
memory: 6228kb
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.302375937266703 481.662711988949468 792.185075601910512 579.954261849419026 807.709446267395720 242.592175484544896 882.267514765530791 530.780780259533230 664.182175960767950 796.360739767358268 662.707167898003945 639.072619279145897 125.821182715263234 745.729175266824768 732.496721809731525 ...
result:
ok 10000 numbers
Test #7:
score: 0
Accepted
time: 259ms
memory: 12700kb
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.497776333199681 1193.960228744214419 1171.242726187862672 1856.289036303557396 2681.882945851288696 1170.870740837989388 1128.361471569933201 1855.878337988720887 3518.324147988294499 1541.786008216372011 1515.015122318711974 1124.406566045259979 2146.716711309011771 1179.430678948048580 1164.1...
result:
ok 100000 numbers
Test #8:
score: -100
Time Limit Exceeded
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:
49999997.019767940044403 49999997.019767940044403 49999997.019767940044403 49999994.039536230266094 49999994.039536230266094 49999997.019767940044403 49999994.039536230266094 50000000.000000000000000 49999994.039536230266094 49999997.019767940044403 49999997.019767940044403 49999994.039536230266094 ...