QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#130414#5433. Absolute DifferencesavacskaWA 2ms5908kbC++235.3kb2023-07-24 06:10:582023-07-24 06:11:01

Judging History

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

  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2023-07-24 06:11:01]
  • 评测
  • 测评结果:WA
  • 用时:2ms
  • 内存:5908kb
  • [2023-07-24 06:10:58]
  • 提交

answer

#include <bits/stdc++.h>
#define pb push_back
#define mp make_pair
#define x first
#define y second

using namespace std;

typedef long long ll;
typedef long double ld;

pair <int, int> Alice[100005], Bob[100005];
ld pref_len[100005], pref_sq[100005], suf_len[100005], suf_sq[100005], pref_cub[100005];

ld point_seg(int x, int lef, int rig)
{
 	if (rig <= x) return (ld) x * (rig - lef) - ((ld) rig * rig - (ld) lef * lef) / 2.0;
 	if (x <= lef) return ((ld) rig * rig - (ld) lef * lef) / 2.0 - (ld) x * (rig - lef);

 	return (ld) x * (x - lef) - ((ld) x * x - (ld) lef * lef) / 2 + ((ld) rig * rig - (ld) x * x) / 2 - (ld) x * (rig - x);
}

ld seg_seg(int l, int r, int L, int R)
{
 	if (R <= l) return (ld) (R - L) * ((ld) r * r - (ld) l * l) / 2.0 - (ld) (r - l) * ((ld) R * R - (ld) L * L) / 2.0;
 	if (L >= r) return (ld) (r - l) * ((ld) R * R - (ld) L * L) / 2.0 - (ld) (R - L) * ((ld) r * r - (ld) l * l) / 2.0;

 	if (l == L && r == R) return (ld) (r - l) * (r - l) * (r - l) / 3;

 	if (r < R) return seg_seg(l, r, L, r) + seg_seg(l, r, r, R);
 	if (l > L) return seg_seg(l, r, L, l) + seg_seg(l, r, l, R);
 	return seg_seg(L, R, l, r);
}

int main()
{
 	//freopen("input.txt", "r", stdin);
 	//freopen("output.txt", "w", stdout);
 	ios_base::sync_with_stdio(0); cin.tie(0);
 	cout.precision(20);

 	int n, m;
 	cin >> n >> m;

 	for (int i = 1; i <= n; i++) cin >> Alice[i].x >> Alice[i].y;
 	for (int i = 1; i <= m; i++) cin >> Bob[i].x >> Bob[i].y;
 	sort(Alice + 1, Alice + n + 1);
 	sort(Bob + 1, Bob + m + 1);

 	bool segA = false, segB = false;
 	for (int i = 1; i <= n; i++) if (Alice[i].x != Alice[i].y) segA = true;
 	for (int i = 1; i <= m; i++) if (Bob[i].x != Bob[i].y) segB = true;

 	if (!segA && !segB)
 	{
 	    ll ans = 0;
 	    ll sumBob = 0;
 	    for (int i = 1; i <= m; i++) sumBob += Bob[i].x;

 	    int uk = 0;
 	    ll sum = 0;
 	    for (int i = 1; i <= n; i++)
 	    {
 	    	while (uk + 1 <= m && Bob[uk + 1].x <= Alice[i].x)
 	    	{
 	    	 	uk++;
 	    	 	sum += Bob[uk].x;
 	    	}
 	    	ans += (ll) uk * Alice[i].x - sum + (sumBob - sum) - (ll) (m - uk) * Alice[i].x;
 	    }

	 	ans = 1.0 * ans / n / m;
	 	cout << fixed << ans << '\n';
	 	return 0;
 	}

 	if (segA && !segB)
 	{
 	 	swap(n, m);
 	 	for (int i = 1; i <= max(n, m); i++) swap(Alice[i], Bob[i]);
 	 	swap(segA, segB);
 	}

 	if (!segA)
 	{
 	 	ld ans = 0;
 	 	ll sumBob = 0;
 	 	for (int i = 1; i <= m; i++) sumBob += Bob[i].y - Bob[i].x;

 	 	for (int i = 1; i <= m; i++)
 	 	{
 	 		pref_len[i] = pref_len[i - 1] + (Bob[i].y - Bob[i].x);
 	 		pref_sq[i] = pref_sq[i - 1] + ((ld) Bob[i].y * Bob[i].y - (ld) Bob[i].x * Bob[i].x) / 2.0;
 	 	}

 	 	for (int i = m; i >= 1; i--)
 	 	{
 	 	 	suf_len[i] = suf_len[i + 1] + (Bob[i].y - Bob[i].x);
 	 	 	suf_sq[i] = suf_sq[i + 1] + ((ld) Bob[i].y * Bob[i].y - (ld) Bob[i].x * Bob[i].x) / 2.0;
 	 	}

 	 	int uk = 0;
 	 	for (int i = 1; i <= n; i++)
 	 	{
 	 		while (uk + 1 <= m && Bob[uk + 1].y <= Alice[i].x) uk++;

 	 		ld pref_val = pref_len[uk] * Alice[i].x - pref_sq[uk];
 	 		ld suf_val = suf_sq[uk + 2] - suf_len[uk + 2] * Alice[i].x;
 	 		ld total = pref_val + suf_val;
 	 		if (uk != m) total += point_seg(Alice[i].x, Bob[uk + 1].x, Bob[uk + 1].y);

 	 		ans += total;
 	 	}
 	 	ans = ans / sumBob / n;
 	 	cout << fixed << ans << '\n';
 	 	return 0;
 	}

 	ll sumAlice = 0, sumBob = 0;
 	for (int i = 1; i <= n; i++) sumAlice += Alice[i].y - Alice[i].x;
 	for (int i = 1; i <= m; i++) sumBob += Bob[i].y - Bob[i].x;

 	for (int i = 1; i <= m; i++)
 	{
 	 	pref_len[i] = pref_len[i - 1] + (Bob[i].y - Bob[i].x) / 2.0;
 	 	pref_sq[i] = pref_sq[i - 1] + ((ld) Bob[i].y * Bob[i].y - (ld) Bob[i].x * Bob[i].x) / 2.0;
 	 	pref_cub[i] = pref_cub[i - 1] + (ld) (Bob[i].y - Bob[i].x) * (Bob[i].y - Bob[i].x) * (Bob[i].y - Bob[i].x) / 6;
 	}

 	for (int i = m; i >= 1; i--)
 	{
 	 	suf_len[i] = suf_len[i + 1] + (Bob[i].y - Bob[i].x) / 2.0;
 	 	suf_sq[i] = suf_sq[i + 1] + ((ld) Bob[i].y * Bob[i].y - (ld) Bob[i].x * Bob[i].x) / 2.0;
 	}

 	int pref = 0, suf = 1;
 	ld ans = 0;
 	for (int i = 1; i <= n; i++)
 	{
 		if (Alice[i].x == Alice[i].y) continue;
 		while (pref + 1 <= m && Bob[pref + 1].y <= Alice[i].x) pref++;
 		while (suf <= m && Bob[suf].x < Alice[i].y) suf++;

 	 	ld pref_val = pref_len[pref] * ((ld) Alice[i].y * Alice[i].y - (ld) Alice[i].x * Alice[i].x) - pref_sq[pref] * (Alice[i].y - Alice[i].x);
 	 	ld suf_val = suf_sq[suf] * (Alice[i].y - Alice[i].x) - suf_len[suf] * ((ld) Alice[i].y * Alice[i].y - (ld) Alice[i].x * Alice[i].x);
 	 	ld total = pref_val + suf_val;

 	 	if (suf - pref >= 2)
 	 	{
 	 	 	int L = pref + 1, R = suf - 1;
 	 	 	total += seg_seg(Alice[i].x, Alice[i].y, Bob[L].x, Bob[L].y);
 	 	 	if (R != L) total += seg_seg(Alice[i].x, Alice[i].y, Bob[R].x, Bob[R].y);
 	 	 	if (R - L >= 2)
 	 	 	{
 	 	 	 	L++, R--;

 	 	 	 	ld free_sl = pref_cub[R] - pref_cub[L - 1];
 	 	 	 	ld sec_sl = pref_sq[R] - pref_sq[L - 1];
 	 	 	 	ld thi_sl = pref_len[R] - pref_len[L - 1];
 	 	 	 	ld val = 2 * free_sl - sec_sl * (Alice[i].x + Alice[i].y) + thi_sl * ((ld) Alice[i].x * Alice[i].x + (ld) Alice[i].y * Alice[i].y);
 	 	 	 	total += val;
 	 	 	}
 	 	}
 	 	ans += total;
 	}

 	ans = ans / sumAlice / sumBob;
 	cout << fixed << ans << '\n';
 	return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 2ms
memory: 5816kb

input:

1 1
0 1
0 1

output:

0.33333333333333333334

result:

ok found '0.333333333', expected '0.333333333', error '0.000000000'

Test #2:

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

input:

1 1
0 1
1 1

output:

0.50000000000000000000

result:

ok found '0.500000000', expected '0.500000000', error '0.000000000'

Test #3:

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

input:

1 1
-1000000000 1000000000
-1000000000 1000000000

output:

666666666.66666666668606922030

result:

ok found '666666666.666666627', expected '666666666.666666627', error '0.000000000'

Test #4:

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

input:

1 1
-1000000000 0
0 1000000000

output:

1000000000.00000000000000000000

result:

ok found '1000000000.000000000', expected '1000000000.000000000', error '0.000000000'

Test #5:

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

input:

1 1
-1000000000 -1000000000
-1000000000 1000000000

output:

1000000000.00000000000000000000

result:

ok found '1000000000.000000000', expected '1000000000.000000000', error '0.000000000'

Test #6:

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

input:

1 1
-999999999 1000000000
-1000000000 -1000000000

output:

1000000000.50000000000000000000

result:

ok found '1000000000.500000000', expected '1000000000.500000000', error '0.000000000'

Test #7:

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

input:

1 1
-1000000000 1000000000
-999999999 -999999999

output:

999999999.00000000052386894822

result:

ok found '999999999.000000000', expected '999999999.000000000', error '0.000000000'

Test #8:

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

input:

1 1
1000000000 1000000000
-1000000000 -1000000000

output:

2000000000

result:

ok found '2000000000.000000000', expected '2000000000.000000000', error '0.000000000'

Test #9:

score: -100
Wrong Answer
time: 2ms
memory: 5876kb

input:

1000 1000
-2175 -2174
-1068 -1065
-1721 -1718
777 834
1162 1169
-3529 -3524
3966 3993
1934 1952
-234 -223
-4967 -4947
8500 8510
5272 5276
-6048 -6033
-34 -22
700 705
-7890 -7886
5538 5543
4114 4126
-9201 -9162
-1521 -1519
-5103 -5100
439 441
993 997
-1684 -1680
-8413 -8404
6724 6728
-3242 -3239
2616...

output:

6628.43462282854439093782

result:

wrong answer 1st numbers differ - expected: '6717.1171457', found: '6628.4346228', error = '0.0132025'