QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#88501#5570. Epidemic Escape5abRE 3ms6180kbC++175.6kb2023-03-16 12:57:452023-03-16 12:57:47

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-16 12:57:47]
  • 评测
  • 测评结果:RE
  • 用时:3ms
  • 内存:6180kb
  • [2023-03-16 12:57:45]
  • 提交

answer

/* name: 5570
 * author: 5ab
 * created at: 2023-03-13
 */
#include <iostream>
#include <algorithm>
#include <iterator>
#include <iomanip>
#include <utility>
#include <cassert>
#include <vector>
#include <limits>
#include <tuple>
#include <cmath>
using namespace std;

typedef long long ll;
using db = long double;

const int max_n = 100000, max_q = 100000, max_k = 5;

inline ll sqr(int x) { return 1ll * x * x; }
struct point
{
	int x, y; ll dis;
	point(int _x = 0, int _y = 0) : x(_x), y(_y), dis(sqr(x) + sqr(y)) { }
	point operator-(const point& rhs) const {
		return point(x - rhs.x, y - rhs.y);
	}
	bool operator==(const point& rhs) {
		return x == rhs.x && y == rhs.y;
	}
};

vector<point> a, b;
vector<vector<point>> hul;
int ck[max_q];
vector<tuple<point, int, ll>> qr;
vector<db> cand[max_q];

inline ll dot(const point& lhs, const point& rhs) { return 1ll * lhs.x * rhs.x + 1ll * lhs.y * rhs.y; }
inline ll cross(const point& lhs, const point& rhs) { return 1ll * lhs.x * rhs.y - 1ll * rhs.x * lhs.y; }

db inters(const point& ln, const point& dr)
{
	if (dot(ln, dr) <= 0)
		return numeric_limits<db>::infinity();
	db coef[2][3] = {
		{ 2. * ln.x, 2. * ln.y, 1. * ln.dis },
		{ 1. * dr.y, -1. * dr.x, 0. }
	};
	if (coef[0][0] == 0)
		swap(coef[0], coef[1]);
	db rto = coef[1][0] / coef[0][0];
	for (int i = 0; i < 3; i++)
		coef[1][i] -= rto * coef[0][i];
	rto = coef[0][1] / coef[1][1];
	for (int i = 0; i < 3; i++)
		coef[0][i] -= rto * coef[1][i];
	// cerr << coef[0][2] / coef[0][0] << " " << coef[1][2] / coef[1][1] << endl;
	return hypot(coef[0][2] / coef[0][0], coef[1][2] / coef[1][1]);
}

signed main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(nullptr);
	
	int n, q, stv = 0;
	
	cin >> n;
	a.reserve(n);
	
	for (int i = 0, x, y; i < n; i++)
	{
		cin >> x >> y;
		if (x == 0 && y == 0)
			stv++;
		else
			a.emplace_back(x, y);
	}
	int sz = a.size();
	assert(unique(a.begin(), a.end()) - a.begin() == sz);
	
	for (int _ = 0; _ < max_k; _++)
	{
		// cerr << _ << " " << a.size() << endl;
		
		hul.emplace_back();
		hul[_].reserve(a.size());
		vector<point>& stk = hul[_];
		
		auto it = min_element(a.begin(), a.end(), [](auto lhs, auto rhs) {
			return lhs.dis < rhs.dis;
		});
		auto stp = *it;
		swap(*it, *a.begin());
		stk.push_back(stp);
		
		vector<tuple<point, ll>> tmp(a.size() - 1);
		transform(a.begin() + 1, a.end(), tmp.begin(), [&](auto x) {
			return make_tuple(x, cross(stp, x));
		});
		sort(tmp.begin(), tmp.end(), [](auto& lhs, auto& rhs) {
			return ((get<1>(lhs) >= 0) ^ (get<1>(rhs) >= 0)) ? 
				get<1>(lhs) > get<1>(rhs) : cross(get<0>(lhs), get<0>(rhs)) > 0;
		});
		
		auto check = [&](point& lp, point& mp, point& rp) {
			return cross(lp, rp) > 0 && 
				__int128(cross(lp, rp)) * dot(rp - mp, lp - mp) +
				__int128(dot(lp, rp)) * cross(rp - mp, lp - mp) >= 0;
		};
		
		for (auto& _$ : tmp)
		{
			auto& pt = get<0>(_$);
			// cerr << pt.x << " " << pt.y << " " << get<1>(_$) << endl;
			while (stk.size() > 1)
			{
				if (cross(stk.back(), pt) == 0 && dot(pt, stk.back()) > 0 && pt.dis < stk.back().dis)
				{
					b.push_back(stk.back());
					stk.pop_back();
				}
				else if (check(end(stk)[-2], stk.back(), pt))
				{
					b.push_back(stk.back());
					stk.pop_back();
				}
				else
					break;
			}
			if (cross(stk.back(), pt) == 0 && dot(pt, stk.back()) > 0 && pt.dis >= stk.back().dis)
				b.push_back(pt);
			else if (check(stk.back(), pt, stk.front()))
				b.push_back(pt);
			else
				stk.push_back(pt);
		}
		a.swap(b);
		if (a.empty())
			break;
		b.clear();
	}
	/*
	for (auto& x : hul)
	{
		for (auto& y : x)
			cerr << "(" << y.x << "," << y.y << ") ";
		cerr << endl;
	}
	*/
	
	cin >> q;
	qr.reserve(q);
	for (int i = 0; i < q; i++)
	{
		int x, y;
		cin >> x >> y >> ck[i];
		if (x != 0 || y != 0)
			qr.emplace_back(point(x, y), i, -1);
	}
	
	for (int _ = 0; _ < max_k && _ < int(hul.size()); _++)
	{
		auto& stk = hul[_];
		int cs = stk.size();
		
		for (auto& x : qr)
			get<2>(x) = cross(stk.front(), get<0>(x));
		sort(qr.begin(), qr.end(), [](auto& lhs, auto& rhs) {
			return ((get<2>(lhs) >= 0) ^ (get<2>(rhs) >= 0)) ? 
				get<2>(lhs) > get<2>(rhs) : cross(get<0>(rhs), get<0>(lhs)) < 0;
		});
		for (int i = 0, j = 0; i < int(qr.size()); i++)
		{
			auto [pt, id, _$] = qr[i];
			// cerr << pt.x << "," << pt.y << endl;
			
			while (dot(stk[j], pt) <= 0 && cross(stk[j], stk[(j + 1) % cs]) > 0)
				j = (j + 1) % cs;
			while (inters(stk[j], pt) > inters(stk[(j + 1) % cs], pt))
				j = (j + 1) % cs;
			// cerr << stk[j].x << " " << stk[j].y << "  " << pt.x << " " << pt.y << endl;
			
			if (cs < (ck[id] - _) * 2)
			{
				for (int l = 0; l < cs; l++)
					cand[id].push_back(inters(stk[l], pt));
			}
			else if (ck[id] - _ > 0)
			{
				for (int tc = 0, aj = j, bj = (j + 1) % cs; tc < ck[id] - _; tc++, aj--, bj++)
				{
					if (aj < 0) aj += cs;
					if (bj == cs) bj = 0;
					// cerr << aj << " " << bj << " ";
					cand[id].push_back(inters(stk[aj], pt));
					cand[id].push_back(inters(stk[bj], pt));
				}
				// cerr << " ---> " << cs << endl;
			}
		}
	}
	
	cout << fixed;
	for (int i = 0; i < q; i++)
	{
		sort(cand[i].begin(), cand[i].end());
		// for (auto x : cand[i])
		// 	cerr << x << " ";
		// cerr << endl;
		if (ck[i] <= stv)
			cout << "0.0000000000";
		else if (int(cand[i].size()) < ck[i] - stv || cand[i][ck[i] - stv - 1] == numeric_limits<db>::infinity())
			cout << "-1";
		else
			cout << setprecision(10) << cand[i][ck[i] - stv - 1];
		cout << "\n";
	}
	
	return 0;
}
// started coding at: 03-13 11:17:16

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 1ms
memory: 6180kb

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: 3ms
memory: 6020kb

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: 6092kb

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: 1ms
memory: 6108kb

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
Dangerous Syscalls

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:


result: