QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#780034#9808. Fragile PinballFRWA 18ms4048kbC++175.3kb2024-11-24 23:49:572024-11-24 23:49:58

Judging History

This is the latest submission verdict.

  • [2024-11-24 23:49:58]
  • Judged
  • Verdict: WA
  • Time: 18ms
  • Memory: 4048kb
  • [2024-11-24 23:49:57]
  • Submitted

answer

#include <bits/stdc++.h>

struct vec
{
	double x, y;

	double len() const { return hypot(x, y); }
	double len2() const;
};
vec operator+(const vec& x, const vec &y) { return {x.x + y.x, x.y + y.y}; }
vec operator-(const vec& x, const vec &y) { return {x.x - y.x, x.y - y.y}; }
double operator*(const vec& x, const vec &y) { return x.x * y.x + x.y * y.y; }
vec operator*(const vec& x, const double &y) { return {x.x * y, x.y * y}; }
vec operator/(const vec& x, const double &y) { return {x.x / y, x.y / y}; }
double det(const vec& x, const vec &y) { return x.x * y.y - x.y * y.x; }

double wedge(const vec& x, const vec &y, const vec &z) { return det(y - x, z - x); }
double area(const vec& x, const vec &y, const vec &z) { return wedge(x, y, z) / 2; }

double vec::len2() const { return *this * *this; }
bool operator==(const vec& x, const vec &y) { return (x - y).len2() < 1E-14; }
bool operator!=(const vec& x, const vec &y) { return (x - y).len2() >= 1E-14; }

vec proj(const vec& dir, const vec &v) { return dir * (dir * v) / dir.len2(); }
vec proj(const vec& x, const vec& y, const vec &p) { return x + proj(y - x, p - x); }
vec refl(const vec& x, const vec& y, const vec &p) { return proj(x, y, p) * 2 - p; }
bool sameray(const vec& x, const vec& y)
{
	return std::abs(det(x, y)) <= 1E-10 && x * y >= 0;
}
bool sbtn(const vec& x, const vec& y, const vec &z)
{
	if (sameray(x, y) || sameray(y, z))
		return false;
	if (det(x, y) < -1E-10 && det(y, z) < -1E-10)
		return false;
	if (det(x, y) < -1E-10 || det(y, z) < -1E-10)
		return det(x, z) < 0;
	return true;
}

bool projon(const vec& dir, const vec &v)
{
	double x = dir * v;
	return 1E-10 < x && x < dir.len2() - 1E-10;
}
bool projon(const vec& x, const vec& y, const vec &p) { return projon(y - x, p - x); }

bool onray(const vec& dir, const vec &v)
{
	auto p = proj(dir, v);
	if (p != v)
		return false;
	return -1E-10 < dir * v;
}
bool onray(const vec& x, const vec& y, const vec &p)
{
	return onray(y - x, p - x);
}

double dist(const vec& x, const vec& y) { return (y - x).len(); }

std::ostream &operator<<(std::ostream &os, const vec &v)
{
	return os << "(" << v.x << ", " << v.y << ")";
}

struct v3
{
	double x, y, z;
	v3(vec v) { x = v.x, y = v.y, z = 1; }
	v3() {} 

	vec norm()
	{
		return {x / z, y / z};
	}
};
v3 cross(const v3 &a, const v3 &b)
{
	v3 res;
	res.x = a.y * b.z - a.z * b.y;
	res.y = a.z * b.x - a.x * b.z;
	res.z = a.x * b.y - a.y * b.x;
	return res;
}

std::pair<bool, vec> inter(const vec& p1, const vec& p2, const vec& q1, const vec& q2)
{
	v3 l1 = cross(v3(p1), v3(p2));
	v3 l2 = cross(v3(q1), v3(q2));
	v3 res = cross(l1, l2);
	if (std::abs(res.z) < 1E-10)
		return {false, {}};
	return {true, res.norm()};
}

vec getpt(const std::vector<vec> &pts, int i)
{
	i %= int(pts.size());
	if (i < 0)
		i += pts.size();
	return pts[i];
}

std::pair<vec, vec> edge(const std::vector<vec> &pts, int i)
{
	return {getpt(pts, i), getpt(pts, i + 1)};
}

double Ans[] = {0, 0, 0, 0, 0, 0, 0};
bool vis[7] = {false, false, false, false, false, false, false};
int en[7];

std::vector<vec> poly[7];

int N;

int chk(int i, int j)
{
	j %= N;
	if (j < 0)
		j += N;
	if (en[i] != -1 && j == en[i])
		return 1;
	if (i != 0 && j == en[i - 1])
		return -1;
	return 0;
}

vec pred(int i, int j);
vec succ(int i, int j);

vec pred(int i, int j)
{
	int x = chk(i, j - 1);
	return x == 0 ? getpt(poly[i], j - 1) : succ(i + x, j);
}

vec succ(int i, int j)
{
	int x = chk(i, j);
	return x == 0 ? getpt(poly[i], j + 1) : pred(i + x, j);
}

void calc1(int r, vec x, vec y)
{
	// std::cout << "!! " << r << ' ' << N << std::endl;
	// std::cout << x << ' ' << y << std::endl;
	// for (int i = 0; i <= r; ++i)
	// {
	// 	for (int j = 0; j < N; ++j)
	// 		std::cout << poly[i][j] << ' ';
	// 	std::cout << std::endl;
	// }
	
	double res = 1E9;
	for (int i = 0; i <= r; ++i)
		for (int j = 0; j < N; ++j)
			if (chk(i, j) == 0)
			{
				auto [q1, q2] = edge(poly[i], j);
				auto [f, p] = inter(x, y, q1, q2);
				if (f && projon(q1, q2, p))
					res = std::min(res, dist(x, p));
			}
	for (int i = 0; i <= r; ++i)
		for (int j = 0; j < N; ++j)
			if (onray(x, y, poly[i][j]))
			{
				vec q0 = pred(i, j), q1 = poly[i][j], q2 = succ(i, j);
				// std::cout << "!! " << q0 << ' ' << q1 << ' ' << q2 << std::endl;
				if (i & 1 ? sbtn(q2 - q1, y - x, q0 - q1) : sbtn(q0 - q1, y - x, q2 - q1))
					res = std::min(res, dist(x, q1));
			}
	assert(res < 1E8);
	// std::cout << res << std::endl;
	// std::cout << std::endl;
	Ans[r] = std::max(Ans[r], res);
}

void calc(int r)
{
	for (int i = 0; i != N; ++i)
	{
		vec pt = poly[0][i];
		for (int jr = 0; jr <= r; ++jr)
		{
			for (int j = 0; j < N; ++j)
			{
				vec y = poly[jr][j];
				if (pt == y)
					break;
				calc1(r, pt, y);
			}
		}
	}
}

void dfs(int r)
{
	en[r] = -1;
	calc(r);
	for (int i = 0; i != N; ++i)
		if (!vis[i])
		{
			en[r] = i;
			vis[i] = true;
			auto [p1, p2] = edge(poly[r], i);
			for (int i = 0; i != N; ++i)
				poly[r + 1][i] = refl(p1, p2, poly[r][i]);
			dfs(r + 1);
			vis[i] = false;
		}
	en[r] = -1;
}

int main()
{
	std::cin >> N;
	for (int i = 0; i != 7; ++i)
		poly[i].resize(N);
	for (auto &pt : poly[0])
		std::cin >> pt.x >> pt.y;
	dfs(0);
	for (int i = 0; i <= N; ++i)
		printf("%.14lf\n", Ans[i]);
}

详细

Test #1:

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

input:

3
4 0
0 3
0 -1

output:

5.00000000000000
8.00000000000000
8.86818503879756
12.21002481088196

result:

ok 4 numbers

Test #2:

score: 0
Accepted
time: 0ms
memory: 3788kb

input:

3
4 0
0 3
0 2

output:

5.00000000000000
5.36656314599950
6.11191913849942
6.78220330441663

result:

ok 4 numbers

Test #3:

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

input:

3
4 0
0 3
0 1

output:

5.00000000000000
6.18465843842649
7.19522354274454
8.65343949929425

result:

ok 4 numbers

Test #4:

score: 0
Accepted
time: 0ms
memory: 4044kb

input:

3
62 -12
-48 100
-45 -96

output:

196.02295783912658
312.04173783276053
326.27847771877617
452.80712372911080

result:

ok 4 numbers

Test #5:

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

input:

3
90 99
-76 -57
99 84

output:

227.79815626997510
274.35230645776346
306.89177947709214
330.10518554643352

result:

ok 4 numbers

Test #6:

score: 0
Accepted
time: 0ms
memory: 4028kb

input:

3
-67 22
-86 12
-81 -12

output:

36.76955262170047
39.56397500565404
50.91685591710601
72.27758551745065

result:

ok 4 numbers

Test #7:

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

input:

3
71 -48
-81 2
-83 -44

output:

160.01249951175689
308.05679456756883
308.05679456756883
308.05679456756883

result:

ok 4 numbers

Test #8:

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

input:

3
44 -44
-31 -77
8 -98

output:

81.93900170248598
115.79266829979316
125.60604402992014
167.93649349697935

result:

ok 4 numbers

Test #9:

score: 0
Accepted
time: 0ms
memory: 3784kb

input:

3
40 91
-42 90
-5 -99

output:

195.25624189766637
378.87426679199888
378.87426679199888
378.87426679199888

result:

ok 4 numbers

Test #10:

score: 0
Accepted
time: 2ms
memory: 4032kb

input:

4
-10 -97
13 -98
90 50
42 97

output:

200.84820138602188
269.68734146533455
382.16606804049610
476.59926283039630
476.59926283039630

result:

ok 5 numbers

Test #11:

score: 0
Accepted
time: 2ms
memory: 3840kb

input:

4
39 89
-72 -94
87 -58
90 36

output:

214.03270778084362
413.74414660992380
413.74414660992380
502.96571824848036
595.01821265490548

result:

ok 5 numbers

Test #12:

score: 0
Accepted
time: 2ms
memory: 3788kb

input:

4
-6 -90
33 -75
4 97
-36 -69

output:

187.26718879718359
269.54944439736869
309.20805779551495
364.70165807157008
395.37828755440637

result:

ok 5 numbers

Test #13:

score: 0
Accepted
time: 2ms
memory: 3788kb

input:

4
44 81
27 81
60 -57
83 3

output:

141.89080308462562
187.12271495993613
251.47668954805476
274.12765684348471
286.31951740573038

result:

ok 5 numbers

Test #14:

score: 0
Accepted
time: 2ms
memory: 3876kb

input:

4
96 -13
99 1
-67 -36
67 -37

output:

170.07351351694948
183.08542624904550
223.21210351724531
277.37918419740191
306.15039727040045

result:

ok 5 numbers

Test #15:

score: 0
Accepted
time: 2ms
memory: 3968kb

input:

4
-18 -98
80 -59
73 68
-78 -62

output:

199.25109786397664
378.32587882437446
378.32587882437451
512.61754381185767
557.38745761591031

result:

ok 5 numbers

Test #16:

score: -100
Wrong Answer
time: 18ms
memory: 3984kb

input:

5
-90 41
-93 27
94 79
83 91
-44 94

output:

194.09533739891847
206.35552445442491
256.73130200089082
337.34690346234032
377.92916040834780
377.92916040834780

result:

wrong answer 6th numbers differ - expected: '396.6629387', found: '377.9291604', error = '0.0472285'