QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#163659#1950. Surveillance1e11AC ✓2ms3788kbC++201.4kb2023-09-04 13:41:592023-09-04 13:42:01

Judging History

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

  • [2023-09-04 13:42:01]
  • 评测
  • 测评结果:AC
  • 用时:2ms
  • 内存:3788kb
  • [2023-09-04 13:41:59]
  • 提交

answer

#include <bits/stdc++.h>
using namespace std;

using i64 = long long;
using dbl = long double;

dbl magic(dbl H, dbl W, dbl h, dbl w){
	dbl a = h / (W - w) / w, b = W * h / (W - w);

	auto f = [&](dbl t){
		return -a * t * t * t / 3 + b * t - t * (-a * t * t + b);
	};

	return f(w) - (b - H > 0 ? f(sqrtl((b - H) / a)) : 0);
}

int main() {
	cin.tie(nullptr)->sync_with_stdio(false);

	auto solve = [&]() {
		dbl H, W, h, w;
		int n; cin >> n;
		vector<pair<int, int>> p(n);
		int mxx = -1e9, mnx = 1e9, mxy = -1e9, mny = 1e9;
		for (auto& [x, y] : p) {
			cin >> x >> y;
			mxx = max(mxx, x);
			mnx = min(mnx, x);
			mxy = max(mxy, y);
			mny = min(mny, y);
		}
		if (n == 4){
			cout << (mxx - mnx) * (mxy - mny) << '\n';
			return;
		}
		set<pair<int, int>> s;
		for (auto x : {mnx, mxx})
			for (auto y : {mny, mxy})
				s.insert(make_pair(x, y));
		for (auto pp : p)
			if (s.find(pp) != s.end())
				s.erase(pp);
		pair<int, int> missing = *s.begin();
		pair<int, int> center;
		for (auto& [x, y] : p){
			if (x != mxx && x != mnx && y != mxy && y != mny){
				center = {x, y};
			}
		}

		W = mxx - mnx, H = mxy - mny;

		w = W - abs(missing.first - center.first), h = H - abs(missing.second - center.second);

		dbl ans = w * h + magic(H, W, h, w) + magic(W, H, w, h);

		cout << fixed << setprecision(20) << ans << '\n';
	};

	solve();

	return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

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

input:

4
-5 6
-5 -2
10 -2
10 6

output:

120

result:

ok found '120.0000000', expected '120.0000000', error '0.0000000'

Test #2:

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

input:

6
627 -788
444 -788
444 -986
-102 -986
-102 -993
627 -993

output:

1597.42268842268842266030

result:

ok found '1597.4226884', expected '1597.4226884', error '0.0000000'

Test #3:

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

input:

6
340 110
340 375
-1000 375
-1000 -135
353 -135
353 110

output:

685643.43814516751433529862

result:

ok found '685643.4381452', expected '685643.4381452', error '0.0000000'

Test #4:

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

input:

6
-182 -316
-182 -286
-672 -286
-672 -353
-580 -353
-580 -316

output:

4677.21852505772103736348

result:

ok found '4677.2185251', expected '4677.2185251', error '0.0000000'

Test #5:

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

input:

6
-745 -431
-374 -431
-374 217
-587 217
-587 411
-745 411

output:

252676.39373556568440903902

result:

ok found '252676.3937356', expected '252676.3937356', error '0.0000000'

Test #6:

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

input:

6
-920 341
-920 227
930 227
930 355
-448 355
-448 341

output:

229417.79463074046748261026

result:

ok found '229417.7946307', expected '229417.7946307', error '0.0000000'

Test #7:

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

input:

6
-939 -133
957 -133
957 334
-69 334
-69 725
-939 725

output:

958691.10477013075967533950

result:

ok found '958691.1047701', expected '958691.1047701', error '0.0000000'

Test #8:

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

input:

6
-175 108
-21 108
-21 -421
82 -421
82 171
-175 171

output:

9897.55834335796528566931

result:

ok found '9897.5583434', expected '9897.5583434', error '0.0000000'

Test #9:

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

input:

6
-306 -342
-235 -342
-235 170
-89 170
-89 548
-306 548

output:

48748.23223458904109506307

result:

ok found '48748.2322346', expected '48748.2322346', error '0.0000000'

Test #10:

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

input:

6
-349 185
-218 185
-218 392
-825 392
-825 -218
-349 -218

output:

284794.98792696408176539080

result:

ok found '284794.9879270', expected '284794.9879270', error '0.0000000'

Test #11:

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

input:

6
-689 -621
551 -621
551 -30
-291 -30
-291 -506
-689 -506

output:

248993.47303745618850712162

result:

ok found '248993.4730375', expected '248993.4730375', error '0.0000000'

Test #12:

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

input:

4
-836 -551
-719 -551
-719 790
-836 790

output:

156897

result:

ok found '156897.0000000', expected '156897.0000000', error '0.0000000'

Test #13:

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

input:

4
276 -742
276 772
-947 772
-947 -742

output:

1851622

result:

ok found '1851622.0000000', expected '1851622.0000000', error '0.0000000'