QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#270980 | #5433. Absolute Difference | ship2077 | WA | 1ms | 12128kb | C++14 | 2.8kb | 2023-12-01 19:21:15 | 2023-12-01 19:21:16 |
Judging History
answer
#include<bits/stdc++.h>
#define x first
#define y second
using namespace std;
typedef long double ld;
constexpr int M=2e5+5;
int n,m,num,suma,sumb,f[M],g[M],lsh[M];
pair<int,int>a[M],b[M];
ld ans,len,sum,Lsh[M],pre1[M],pre2[M];
int read(){
int x=0,f=1;char ch=getchar();
while (!isdigit(ch)) {if (ch=='-') f=-1;ch=getchar();}
while (isdigit(ch)) x=x*10+ch-48,ch=getchar();
return x*f;
}
ld calc(ld x1,ld y1,ld x2,ld y2){
return (y1-x1)*(y2-x2)*(x2+y2-y1-x1)*0.5;
}
ld Calc(ld len){return len*len*len/3.0;}
void subtask1(){ len=n*m;
for (int i=1;i<=m;i++) sum+=b[i].x/len;
for (int i=1,j=0;i<=n;i++){
while (j<m&&b[j+1].x<=a[i].x)
sum-=b[++j].x*2/len;
ans+=a[i].x*(j*2-m)/len+sum;
}
printf("%.15Lf\n",ans);
}
void subtask2(){
if (suma) swap(n,m),swap(a,b),swap(suma,sumb);
for (int i=1;i<=n;i++) lsh[++num]=a[i].x;
for (int i=1;i<=m;i++) lsh[++num]=b[i].x,lsh[++num]=b[i].y;
sort(lsh+1,lsh+num+1);num=unique(lsh+1,lsh+num+1)-lsh-1;
for (int i=1;i<=n;i++) f[lower_bound(lsh+1,lsh+num+1,a[i].x)-lsh]=1;
for (int i=1;i<=m;i++)
g[lower_bound(lsh+1,lsh+num+1,b[i].x)-lsh]++,
g[lower_bound(lsh+1,lsh+num+1,b[i].y)-lsh]--;
for (int i=1;i<=num;i++) g[i]+=g[i-1];
for (int i=1;i<=num;i++)
if (!f[i]) pre1[i]=pre1[i-1],pre2[i]=pre2[i-1];
else pre1[i]=pre1[i-1]+lsh[i],
pre2[i]=pre2[i-1]+1;
for (int i=1;i<=num;i++)
if (g[i])
ans+=(lsh[i+1]*lsh[i+1]-lsh[i]*lsh[i])*(pre2[i]-pre2[num]*0.5)
+(-pre1[i]+(pre1[num]-pre1[i]))*(lsh[i+1]-lsh[i]);
printf("%.15Lf\n",ans/n/sumb);
}
void subtask3(){
for (int i=1;i<=n;i++) lsh[++num]=a[i].x,lsh[++num]=a[i].y;
for (int i=1;i<=m;i++) lsh[++num]=b[i].x,lsh[++num]=b[i].y;
sort(lsh+1,lsh+num+1);num=unique(lsh+1,lsh+num+1)-lsh-1;
for (int i=1;i<=num;i++) Lsh[i]=(ld)lsh[i]/suma/sumb;
for (int i=1;i<=n;i++)
f[lower_bound(lsh+1,lsh+num+1,a[i].x)-lsh]++,
f[lower_bound(lsh+1,lsh+num+1,a[i].y)-lsh]--;
for (int i=1;i<=m;i++)
g[lower_bound(lsh+1,lsh+num+1,b[i].x)-lsh]++,
g[lower_bound(lsh+1,lsh+num+1,b[i].y)-lsh]--;
for (int i=1;i<=num;i++) f[i]+=f[i-1],g[i]+=g[i-1];
for (int i=1;i<=num;i++)
if (!g[i]) pre1[i]=pre1[i-1],pre2[i]=pre2[i-1];
else pre1[i]=pre1[i-1]+(lsh[i]-lsh[i+1])*(lsh[i]+lsh[i+1]),
pre2[i]=pre2[i-1]+lsh[i+1]-lsh[i];
for (int i=1;i<=num;i++) if (f[i])
ans+=(-pre1[num]+pre1[i]+pre1[i-1]+(-pre2[num]+pre2[i]+pre2[i-1])*(lsh[i]+lsh[i+1]))*(lsh[i+1]-lsh[i])*0.5;
for (int i=1;i<=num;i++)
if (f[i]&&g[i]) ans+=Calc(lsh[i+1]-lsh[i]);
printf("%.15Lf\n",ans/suma/sumb);
}
int main(){
n=read();m=read();
for (int i=1;i<=n;i++) a[i]={read(),read()},suma+=a[i].y-a[i].x;
for (int i=1;i<=m;i++) b[i]={read(),read()},sumb+=b[i].y-b[i].x;
sort(a+1,a+n+1);sort(b+1,b+m+1);
if (!suma&&!sumb) return subtask1(),0;
if (!suma||!sumb) return subtask2(),0;
return subtask3(),0;
}
详细
Test #1:
score: 100
Accepted
time: 0ms
memory: 12128kb
input:
1 1 0 1 0 1
output:
0.333333333333333
result:
ok found '0.333333333', expected '0.333333333', error '0.000000000'
Test #2:
score: 0
Accepted
time: 0ms
memory: 8860kb
input:
1 1 0 1 1 1
output:
0.500000000000000
result:
ok found '0.500000000', expected '0.500000000', error '0.000000000'
Test #3:
score: 0
Accepted
time: 1ms
memory: 12124kb
input:
1 1 -1000000000 1000000000 -1000000000 1000000000
output:
666666666.666666666686069
result:
ok found '666666666.666666627', expected '666666666.666666627', error '0.000000000'
Test #4:
score: -100
Wrong Answer
time: 0ms
memory: 12116kb
input:
1 1 -1000000000 0 0 1000000000
output:
499999999.256690687994706
result:
wrong answer 1st numbers differ - expected: '1000000000.0000000', found: '499999999.2566907', error = '0.5000000'