QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#68070#75. Build the Perfect HouseYunanWA 225ms3648kbC++172.3kb2022-12-14 14:30:082022-12-14 14:30:10

Judging History

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

  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2022-12-14 14:30:10]
  • 评测
  • 测评结果:WA
  • 用时:225ms
  • 内存:3648kb
  • [2022-12-14 14:30:08]
  • 提交

answer

#include <bits/stdc++.h>

using namespace std;

const long double pi = acos(- 1);

bool equals(long double a, long double b)
{
	return abs(a - b) <= 1e-12;
}

struct point
{
	long double x, y;
	point() {}
	point(const long double &a, const long double &b)
	{
		x = a, y = b;
	}
	long double dist(const point &a)
	{
		return hypot(x - a.x, y - a.y);
	}
	point rotating(const point &a, const long double &b)
	{
		long double xx = (x - a.x) * cos(b) - (y - a.y) * sin(b);
		long double yy = (x - a.x) * sin(b) + (y - a.y) * cos(b);
		return point(xx + a.x, yy + a.y);
	}
};

int main()
{
	ios_base :: sync_with_stdio(false); cin.tie(0); cout.tie(0);
	#ifndef  ONLINE_JUDGE
	freopen("test.inp", "r", stdin);
	freopen("test.out", "w", stdout);
	#endif
	int n;
	cin >> n;
	vector <point> p(n);
	for (int i = 0; i < n; ++i)
		cin >> p[i].x >> p[i].y;
	long double l = 2.0, r = 1e18;
	int cnt = 0;
	while (equals(l , r) == false && (++cnt) <= 499)
	{
		long double m = (l + r) / 2.0;
		bool checking = true;
		long double left = 0.0, right = pi / 2.0, down = pi / 2.0, up = 0.0;
		for (int i = 0; i < n; ++i)
		{
			long double d = p[i].dist(point(0.0, 0.0));
			if (equals(d, m / 2.0) == false && d < m / 2.0)
			{
				checking = false;
				break;
			}
			if (equals(d, m / sqrt(2.0)) == true || d > m / sqrt(2.0))
				continue;
			long double angle = atan2(p[i].y, p[i].x);
			if (angle < 0)
				angle += pi;
			if (angle >= pi / 2.0 && angle <= pi)
				angle -= pi / 2.0;
			long double arccos = acos(m / (2.0 * d));
			long double arcsin = asin(m / (2.0 * d));
			long double l = m / 2.0;
			if (- l < p[i].x && p[i].x < l && - l < p[i].y && p[i].y < l)
			{
				left = max(left, angle - arccos);
				right = min(right, angle + arccos);
				if (left > right)
				{
					checking = false;
					break;
				}
			}
			else
			{
				if (angle <= pi * 0.75)
				{
					down = min(down, angle + arccos);
					up = max(up, angle - arccos + pi / 2.0);
				}
				else
				{
					down = min(down, angle - arcsin);
					up = max(up, angle - arccos);
				}
			}
			if (left > down && right < up)
			{
				checking = false;
				break;
			}
		}
		if (checking == true)
			l = m;
		else
			r = m;
	}
	cout << fixed << setprecision(4) << l * 4.0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

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

input:

1
0 1

output:

8.0000

result:

ok single line: '8.0000'

Test #2:

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

input:

1
737150196 19121149

output:

5899185190.1193

result:

ok single line: '5899185190.1193'

Test #3:

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

input:

10
966443346 -756724170
-994135047 221603380
-678639837 -178769228
-530862694 752762268
-768046638 -463257882
237914061 265304072
224472503 67786657
-722418124 437150660
280931601 982655876
-100691338 -575414914

output:

1875875227.7538

result:

ok single line: '1875875227.7538'

Test #4:

score: 0
Accepted
time: 4ms
memory: 3628kb

input:

100
-807307593 -329027676
29978288 -862282581
199507100 -804875516
756164111 -476914400
388885868 -607655729
268853606 7189787
882419844 -982342495
814289624 -409509654
-552136630 -393924002
387395089 -390056676
-46897750 824082471
-843687211 -808855940
320898921 362841693
-562978010 945412567
19277...

output:

747010080.6848

result:

ok single line: '747010080.6848'

Test #5:

score: 0
Accepted
time: 225ms
memory: 3648kb

input:

10000
-216971808 -400844991
-733662179 -109297508
-474740941 323301341
-33501332 -26194214
-489374896 -91235544
-241666129 546977023
428695487 -71876660
-919475897 674465201
-312547937 -246492172
-689708208 479300243
924021252 -151522527
905289986 -588504604
-88124297 -253183079
-362469880 91566969
...

output:

67588490.1808

result:

ok single line: '67588490.1808'

Test #6:

score: -100
Wrong Answer
time: 1ms
memory: 3636kb

input:

100
-80 58
-68 -72
-47 88
-76 -63
6 100
59 -80
84 54
93 37
81 -58
100 6
37 93
100 0
100 -5
25 96
-98 -12
91 -41
54 -84
-87 48
85 -52
-87 -48
-5 100
59 81
-72 -67
48 -86
-90 42
-53 85
-89 -42
18 -97
-72 68
-99 -6
-36 -92
95 -29
-5 -99
69 -72
31 -94
69 73
-80 -57
6 -99
-62 -76
53 85
31 95
0 100
77 -63...

output:

696.0000

result:

wrong answer 1st lines differ - expected: '579.2322', found: '696.0000'