QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#153673#5433. Absolute Differencevalue0WA 2ms4180kbC++205.8kb2023-08-30 18:30:452023-08-30 18:30:46

Judging History

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

  • [2023-08-30 18:30:46]
  • 评测
  • 测评结果:WA
  • 用时:2ms
  • 内存:4180kb
  • [2023-08-30 18:30:45]
  • 提交

answer

#include<bits/stdc++.h>
using namespace std;
using ll = long long;
using ld = long double;
#define double ld
ll n,m;
ld s = 0;
const ld eps = 1e-9;
struct edge
{
	ld l,r,len;
	
	bool operator < (edge t)
	{
		if(t.l != l)
		{
			return l < t.l;
		}
		return r < t.r;
	}
};


void solve()
{
	cin>>n>>m;
	vector<edge> a(n + 1),b(m + 1);
	vector<ld> a1(n + 1),a2(n + 1),b1(m + 1),b2(m + 1),la(n + 1),lb(m + 1);
	for(int i = 1;i<=n;i++)
	{
		scanf("%Lf %Lf",&a[i].l,&a[i].r);
		a[i].len = a[i].r - a[i].l;
//		cout<<a[i].len<<endl;
	}
	for(int i = 1;i<=m;i++)
	{
		scanf("%Lf %Lf",&b[i].l,&b[i].r);
		b[i].len = b[i].r - b[i].l;
	}
	sort(a.begin() + 1,a.end());
	sort(b.begin() + 1,b.end());
	for(int i = 1;i<=n;i++)
	{
		a1[i] = a1[i-1] + a[i].r - a[i].l;
		a2[i] = a2[i-1] + a[i].r * a[i].r - a[i].l * a[i].l;
		la[i] = la[i-1] + a[i].len;
	}
	for(int i = 1;i<=m;i++)
	{
		b1[i] = b1[i-1] + b[i].r - b[i].l;
		b2[i] = b2[i-1] + (b[i].r * b[i].r - b[i].l * b[i].l);
		lb[i] = lb[i-1] + b[i].len;
	}
//	cout<<la[n]<<' '<<lb[m]<<endl;
	s = la[n] * lb[m];
//	cout<<la[n]<<endl;
	ld ans = 0;

	if(la[n] == 0 || lb[m] == 0)
	{
		if(la[n] == 0 && lb[m] == 0)
		{
			for(int i = 1;i<=m;i++)
			{
				lb[i] = lb[i-1] + b[i].l;
			}
			for(int i = 1;i<=n;i++)
			{
				ans += abs(a[i].l * m - lb[m]);
			}
			s = n * m;
			printf("%.12Lf",ans / s);
			return;
		}
		else if(la[n] == 0)
		{
			for(int i= 1;i<=n;i++)
			{
				ld c = a[i].l;
				ll l = 0;
				ll r = m + 1;
				while(l + 1 < r)
				{
					ll mid = l + r >> 1;
					if(b[mid].r <= c)
					{
						l = mid;
					}
					else
					{
						r = mid;
					}
				}
//				cout<<l<<endl;
				ans += c * (b1[l]) - (ld)1.0 / 2 * (b2[l]);
//				cout<<ans<<endl;
				ll st = l + 1;
				l = 0;
				r = m + 1;
				while(l + 1 < r)
				{
					ll mid = l + r >> 1;
					if(b[mid].l >= c)
					{
						r = mid;
					}
					else
					{
						l = mid;
					}
				}
				ans -= c * (b1[m] - b1[r - 1]) - (ld)1.0 / 2 * (b2[m] - b2[r-1]);
//				cout<<ans<<endl;
				while(st < r && st <= m)
				{
					ld t = b[st].l;
					ld d = b[st].r;
					ans += c * c - c * (t + d) + (ld)1.0 / 2 * (t * t + d * d);
					st ++;
				}
			}
			s = n * lb[m];
			printf("%.12Lf",ans / s);
			return ;
		}
		else
		{
			for(int i= 1;i<=m;i++)
			{
				ld c = b[i].l;
				ll l = 0;
				ll r = n + 1;
				while(l + 1 < r)
				{
					ll mid = l + r >> 1;
					if(a[mid].r <= c)
					{
						l = mid;
					}
					else
					{
						r = mid;
					}
				}
//				cout<<l<<endl;
				ans += c * (a1[l]) - (ld)1.0 / 2 * (a2[l]);
//				cout<<ans<<endl;
				ll st = l + 1;
				l = 0;
				r = n + 1;
				while(l + 1 < r)
				{
					ll mid = l + r >> 1;
					if(a[mid].l >= c)
					{
						r = mid;
					}
					else
					{
						l = mid;
					}
				}
				ans -= c * (a1[n] - a1[r - 1]) - (ld)1.0 / 2 * (a2[n] - a2[r-1]);
//				cout<<ans<<endl;
				while(st < r && st <= n)
				{
					ld t = a[st].l;
					ld d = a[st].r;
					ans += c * c - c * (t + d) + (ld)1.0 / 2 * (t * t + d * d);
					st ++;
				}
			}
//			cout<<ans<<endl;
			s = m * la[n];
//			cout<<s<<endl;
			printf("%.12Lf",ans / s);
			return ;
		}
	}
	auto calc = [&](edge tb,edge ta)
	{
		ld res = 0;
//		cout<<ta.l<<' '<<ta.r<<endl;
//		cout<<tb.l<<' '<<tb.r<<endl<<endl;
		res = ((ld)1.0 / 2 * (ta.r * ta.r - ta.l * ta.l) * (tb.r - tb.l) - (1.0 / 2 * (ta.r - ta.l) * (tb.r * tb.r - tb.l * tb.l)));
		return res;
		
	};
//	auto calc1 = [&](ld x,ld a,ld b)
//	{
//		ld res = 0;
////		cout<<ta.l<<' '<<ta.r<<endl;
////		cout<<tb.l<<' '<<tb.r<<endl<<endl;
//		res = x * x - x * a - x * b + 1.0 / 2 * a * a + 1.0 / 2 * b * b;
//		return res;
//		
//	};
//	edge s1,s2;
//	s1.l = 1;
//	s1.r = 3;
//	s2.l = 0;
//	s2.r = 1;
//	cout<<calc(s2,s1) / 2<<endl;
//	double res = 0;
	for(int i = 1;i<=n;i++)
	{
//		ans = 0;
		ll l = 0;
		ll r = m + 1;
		while(l + 1 < r)
		{
			ll mid = l + r >> 1;
			if(b[mid].r <= a[i].l)
			{
//				cout<<b[mid].r<<' '<<a[i].l<<endl;
				l = mid;
			}
			else
			{
				r = mid;
			}
		}
		ans += ((ld)1.0 / 2 * ((a2[i] - a2[i-1]) * b1[l]) - 1.0 / 2 * ((a1[i] - a1[i-1]) * b2[l]));
		ll st = l + 1;
//		cout<<st<<endl;
//		cout<<l<<endl;
		l = 0;
		r = m + 1;
		while(l + 1 < r)
		{
			ll mid = l + r >> 1;
			if(b[mid].l >= a[i].r)
			{
				r = mid;
			}
			else
			{
				l = mid;
			}
		}
//		cout<<r<<endl;
//		cout<<b2[m] - b2[r - 1]<<endl;
//		cout<<(1.0 / 2 * ((a2[i] - a2[i-1]) * (b1[m] - b1[r-1])) - 1.0 / 2 * ((a1[i] - a1[i-1]) * (b2[m] - b2[r - 1])))<<endl;
//		cout<<ans<<endl;
		ans -= ((ld)1.0 / 2 * ((a2[i] - a2[i-1]) * (b1[m] - b1[r-1])) - 1.0 / 2 * ((a1[i] - a1[i-1]) * (b2[m] - b2[r - 1]))) ;
//		cout<<st<<endl;
		while(st < r && st <= m && b[st].l < a[i].r)
		{
//			cout<<1<<endl;
			edge ta,tb,tc;
			ta.l = min(a[i].l,b[st].l);
			ta.r = max(a[i].l,b[st].l);
			tb.l = ta.r;
			tb.r = min(a[i].r,b[st].r);
			tc.l = tb.r;
			tc.r = max(a[i].r,b[st].r);
//			cout<<ta.l<<' '<<ta.r<<endl;
//			cout<<tb.l<<' '<<tb.r<<endl;
//			cout<<tc.l<<' '<<tc.r<<endl;
			if(ta.l != tb.l)
			{
				ans += calc(ta,tb);

			}
			if(tb.r != tc.r)
			{
				ans += calc(tb,tc);
	
			}
			if(ta.l != tb.l && tb.r != tc.r)
			{
				if((ta.l == a[i].l && tc.r == b[st].r) || (ta.l == b[st].l && tc.r == a[i].r))
				{
					ans += calc(ta,tc);
				}
			}
//			cout<<ans<<endl;
//			cout<<tb.l<<' '<<tb.r<<' '<<s<<endl;
			ans += 2 * (((ld)1.0 / 6 * (pow(tb.r,3) - pow(tb.l,3))) - (1.0 / 2 * tb.l *pow(tb.r,2)) + (1.0 / 2 * pow(tb.l,2) * tb.r));
			st ++;
		}
//		res += ans /(a[i].len ** la[n];
	}
//	cout<<ans<<endl;
	printf("%.12Lf",ans / s);
}

int main()
{
	int t = 1;
	while(t--)
	{
		solve();
	}
	return 0;
}

詳細信息

Test #1:

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

input:

1 1
0 1
0 1

output:

0.333333333333

result:

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

Test #2:

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

input:

1 1
0 1
1 1

output:

0.500000000000

result:

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

Test #3:

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

input:

1 1
-1000000000 1000000000
-1000000000 1000000000

output:

666666666.666666666686

result:

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

Test #4:

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

input:

1 1
-1000000000 0
0 1000000000

output:

1000000000.000000000000

result:

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

Test #5:

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

input:

1 1
-1000000000 -1000000000
-1000000000 1000000000

output:

1000000000.000000000000

result:

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

Test #6:

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

input:

1 1
-999999999 1000000000
-1000000000 -1000000000

output:

1000000000.500000000000

result:

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

Test #7:

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

input:

1 1
-1000000000 1000000000
-999999999 -999999999

output:

999999999.000000000524

result:

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

Test #8:

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

input:

1 1
1000000000 1000000000
-1000000000 -1000000000

output:

2000000000.000000000000

result:

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

Test #9:

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

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:

6717.117145739454

result:

ok found '6717.117145739', expected '6717.117145739', error '0.000000000'

Test #10:

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

input:

1000 1000
-5010 -4999
-2128 -2113
-5798 -5765
705 713
-3956 -3938
-5308 -5307
6759 6772
-772 -770
-860 -859
2308 2323
-5500 -5500
5140 5177
-6747 -6733
7509 7511
8864 8870
-6382 -6374
1901 1904
-5763 -5760
3019 3027
2962 2963
-314 -301
-222 -203
-726 -724
-62 -58
-1203 -1195
-5216 -5215
-4298 -4292
...

output:

6682.581127471436

result:

ok found '6682.581127471', expected '6682.581127471', error '0.000000000'

Test #11:

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

input:

1000 1000
770 770
5869 5869
-8786 -8786
7549 7549
-4165 -4165
4023 4023
-9779 -9779
7797 7797
1105 1105
508 508
7653 7653
-359 -359
9393 9393
-9363 -9363
-4160 -4160
-3682 -3682
9409 9409
-8548 -8548
-9908 -9908
-7494 -7494
3751 3751
2326 2326
-3311 -3311
3651 3651
-7663 -7663
5376 5376
-7071 -7071
...

output:

6673.756816891039

result:

ok found '6673.756816891', expected '6673.756816891', error '0.000000000'

Test #12:

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

input:

1000 1000
-735 -735
-829 -829
-6376 -6376
8558 8558
155 155
5533 5533
8800 8800
-1738 -1738
919 919
52 52
2076 2076
-6911 -6911
139 139
6733 6733
9923 9923
-4619 -4619
-9429 -9429
9902 9902
-5984 -5984
2580 2580
8738 8738
7960 7960
3388 3388
-2689 -2689
7986 7986
2565 2565
-8908 -8908
9359 9359
-434...

output:

4923.426856000000

result:

wrong answer 1st numbers differ - expected: '6479.3846800', found: '4923.4268560', error = '0.2401398'