QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#153667#5433. Absolute Differencevalue0WA 1ms3888kbC++205.9kb2023-08-30 18:08:392023-08-30 18:08:39

Judging History

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

  • [2023-08-30 18:08:39]
  • 评测
  • 测评结果:WA
  • 用时:1ms
  • 内存:3888kb
  • [2023-08-30 18:08:39]
  • 提交

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[n] == 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 - 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 a = b[st].l;
					ld d = b[st].r;
					ans += c * (a - d) + (ld)1.0 / 2 * (a * a + 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 * (t - d) + (ld)1.0 / 2 * (t * t + d * d);
					st ++;
				}
			}
			s = m * la[n];
			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<<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)
		{
			if(abs(b[st].len) <= eps && abs(a[i].len) <= eps)
			{
				cout<<1<<endl;
				ans += abs(b[st].l - a[i].l);
			}
			else if(b[st].len == 0)
			{
				ans += calc1(b[st].l,a[i].l,a[i].r);
			}
			else if(a[i].len == 0)
			{
				ans += calc1(a[i].l,b[st].l,a[st].r);
			}
			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: 0
Wrong Answer
time: 1ms
memory: 3888kb

input:

1 1
0 1
0 1

output:

0.000000000000

result:

wrong answer 1st numbers differ - expected: '0.3333333', found: '0.0000000', error = '0.3333333'