QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#87780#5570. Epidemic EscapeappleseTL 441ms17416kbC++146.7kb2023-03-14 10:00:322023-03-14 10:00:36

Judging History

你现在查看的是最新测评结果

  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2023-03-14 10:00:36]
  • 评测
  • 测评结果:TL
  • 用时:441ms
  • 内存:17416kb
  • [2023-03-14 10:00:32]
  • 提交

answer

#include<bits/stdc++.h>
using namespace std;
const int maxn = 1e5 + 5;
const long double eps = 1e-8;
int Dcmp(long double x) {
	return x < -eps ? -1 : x > eps ? 1 : 0;
}
struct Point {
	long double x, y;
	int id;
	Point(long double x = 0, long 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 long double &k) const {
		return Point(x * k, y * k);
	}
	Point operator / (const long double &k) const {
		return Point(x / k, y / k);
	}
	long double operator * (const Point &rhs) const {
		return x * rhs.x + y * rhs.y;
	}
	long double operator ^ (const Point &rhs) const {
		return x * rhs.y - y * rhs.x;
	}
	long double len2() {
		return x * x + y * y;
	}
	long double len() {
		return sqrt(len2());
	}
	Point Unit() {
		return *this / len();
	}
}p[maxn];
long 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;
}
long 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 {
	long double dd;
	int hullid, id;
	Node(long 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<long 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();
			long double nowl = w.len();
			long 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]);
		}
	}
	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();
		long 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: %.15Lf 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])))
						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])))
						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])))
						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])))
						dismax[i] = x;
				}
				// for(int j = 0; j < sz[i]; ++ j) {
				// 	if(Dcmp(Dis(now, nowp, hull[i][dismax[i]]) < Dis(now, nowp, hull[i][j])))
				// 		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]));
		}
		long double ans = 1e18;
		for(int c = 1; c <= k; ++ c) {
			Node w = que.top();
			que.pop();
// cerr << w.dd << " " << w.hullid << " " << w.id << endl;
			if(Dcmp(w.dd + newl) <= 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)
			puts("-1");
		else
			// printf("%lld\n", (long long)round(invr * invr / ans / 2 * 1e7));
			printf("%.15Lf\n", invr * invr / ans / 2);
	}
}

详细

Test #1:

score: 100
Accepted
time: 4ms
memory: 8336kb

input:

5
5 -3
5 4
-6 2
-5 0
4 1
2
-3 -10 1
6 -9 1

output:

8.700255424092125
3.226019562257254

result:

ok 2 numbers

Test #2:

score: 0
Accepted
time: 1ms
memory: 8332kb

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.167762968124702
26.162950903902258
5.461488320163312
6.363961030678928
-1
5.289408221642574
3.726779962499649
4.609772228646444
2.929442379201411
4.761728940206488

result:

ok 10 numbers

Test #3:

score: 0
Accepted
time: 1ms
memory: 8388kb

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.000000000000000
5.130527658008168
-1
-1
-1
3.535533905932738
2.236067977499790
11.985407794480754
15.320646925708530
3.535533905932738
2.462740091320326
4.527692569068708
3.762998305872592
15.320646925708530
2.981423969999720
5.621703504797989
7.071067811865475
2.735793833832251
-1
8.125000000000000

result:

ok 20 numbers

Test #4:

score: 0
Accepted
time: 5ms
memory: 8464kb

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.758678868757292
29.571405997861689
24.622144504490262
27.771745654730640
26.678366712896510
24.423702460472158
28.893348196396304
29.776169557758460
31.940362970515170
27.214901602377858
31.728095045748501
27.071160551681187
25.299110030617503
26.871065152124929
28.995839453427890
28.356314246197...

result:

ok 100 numbers

Test #5:

score: 0
Accepted
time: 38ms
memory: 9412kb

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.154917004616741
2.167265935742733
2.067643085494710
2.111841978749801
2.111841978749801
2.111841978749801
2.124987278610405
2.121320343559643
2.027587510099407
2.092882282881672
2.141537214391802
2.061552812808830
2.154917004616741
2.000000000000000
2.121320343559643
2.167265935742733
2.0676430854...

result:

ok 10000 numbers

Test #6:

score: 0
Accepted
time: 49ms
memory: 8924kb

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.302375937283462
481.662711989051543
792.185075601818101
579.954261849271026
807.709446267823716
242.592175484557133
882.267514766716480
530.780780259741773
664.182175961040407
796.360739767517053
662.707167898652724
639.072619278743947
125.821182715262998
745.729175266718933
732.496721810003200
...

result:

ok 10000 numbers

Test #7:

score: 0
Accepted
time: 441ms
memory: 17416kb

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.497776332412405
1193.960228745127131
1171.242726187058480
1856.289036299032395
2681.882945853968047
1170.870740836292072
1128.361471572151294
1855.878337989198021
3518.324147970202143
1541.786008215450495
1515.015122316480815
1124.406566046596429
2146.716711313765066
1179.430678947102001
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:

49999995.835242208544514
49999995.899270624966448
50000007.246854834065743
49999996.276165170398599
50000024.378835468629404
49999996.485712719353614
50000002.594606619855767
50000024.194025965694891
49999995.724647671479033
50000017.543795155012049
50000016.964628529200127
50000003.015157017140154
...

result: