QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#87740#5570. Epidemic Escape5abWA 2ms9216kbC++175.2kb2023-03-14 08:22:342023-03-14 08:22:38

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 08:22:38]
  • 评测
  • 测评结果:WA
  • 用时:2ms
  • 内存:9216kb
  • [2023-03-14 08:22:34]
  • 提交

answer

/* name: 5570
 * author: 5ab
 * created at: 2023-03-13
 */
#include <iostream>
#include <algorithm>
#include <iterator>
#include <iomanip>
#include <utility>
#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);
	}
};

vector<point> a, b;
vector<vector<point>> hul;
int ck[max_q];
tuple<point, int, ll> qr[max_q];
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);
	}
	
	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>(rhs), get<0>(lhs)) < 0;
		});
		
		for (auto& _$ : tmp)
		{
			auto& pt = get<0>(_$);
			// cerr << pt.x << " " << pt.y << " " << get<1>(_$) << endl;
			while (stk.size() > 1)
			{
				if (cross(pt, stk.back()) == 0 && dot(pt, stk.back()) > 0 && pt.dis < stk.back().dis)
				{
					b.push_back(stk.back());
					stk.pop_back();
				}
				else if (cross(end(stk)[-2], pt) > 0 && 
				__int128(cross(end(stk)[-2], pt)) * dot(pt - stk.back(), end(stk)[-2] - stk.back()) +
				__int128(dot(end(stk)[-2], pt)) * cross(pt - stk.back(), end(stk)[-2] - stk.back()) >= 0)
				{
					b.push_back(stk.back());
					stk.pop_back();
				}
				else
					break;
			}
			if (cross(pt, stk.back()) == 0 && dot(pt, stk.back()) > 0 && pt.dis >= stk.back().dis)
				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;
	for (int i = 0; i < q; i++)
	{
		int x, y;
		cin >> x >> y >> ck[i];
		qr[i] = make_tuple(point(x, y), i, -1);
	}
	
	for (int _ = 0; _ < max_k && _ < int(hul.size()); _++)
	{
		auto& stk = hul[_];
		int cs = stk.size();
		
		for (int i = 0; i < q; i++)
			get<2>(qr[i]) = cross(stk.front(), get<0>(qr[i]));
		sort(qr, qr + q, [](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 < q; i++)
		{
			auto [pt, id, _$] = qr[i];
			
			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
			{
				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 (int(cand[i].size()) < ck[i] || cand[i][ck[i] - 1] == numeric_limits<db>::infinity())
			cout << "-1";
		else
			cout << setprecision(10) << cand[i][ck[i] - 1];
		cout << "\n";
	}
	
	return 0;
}
// started coding at: 03-13 11:17:16

详细

Test #1:

score: 100
Accepted
time: 0ms
memory: 9048kb

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: 0ms
memory: 9216kb

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: 0ms
memory: 9200kb

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: -100
Wrong Answer
time: 2ms
memory: 9088kb

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
30.4540010599
25.1496681332
28.3011569706
28.6117519545
26.690...

result:

wrong answer 18th numbers differ - expected: '25.6496237', found: '30.4540011', error = '0.1873079'