P6149题解

Alies_FP · 2023-12-25 22:49:44 · 题解

P6149题

中文与英文、数字或公式之间以半角空格隔开，但中文标点符号与英文、数字或公式之间不应有空格。

这是一道简单的题。

考虑使用暴力枚举，那么数据量 10^5，时间复杂度 O(n^3)，必然超时。

考虑下图：（来自题解）

此时，总面积为：(a + b + c) \times d + (b + c) \times d + c \times d + (a + b + c) \times (d + e) + (b + c) \times (d + e) + (a + b + c) \times (d + e + f) + (b + c) \times (d + e + f) + c \times (d + e + f)=(a + 2 \times b + 3 \times c) \times (f + 2 \times e + 3 \times d)

时间复杂度为 O(n^2)，算法可行。

具体代码：

#include <bits/stdc++.h>
using namespace std;
int n,cnt_x[100005],cnt_y[100005],last_x[100005],last_y[100005];
long long ans,sum_x[100005],sum_y[100005];
struct fd{
    int x,y;
}a[100005];
bool cmp1(fd a,fd b){
    return a.x<b.x||(a.x==b.x&&a.y<b.y);
}
bool cmp2(fd a,fd b){
    return a.x<b.x||(a.x==b.x&&a.y>b.y);
}
bool cmp3(fd a,fd b){
    return a.x>b.x||(a.x==b.x&&a.y<b.y);
}
bool cmp4(fd a,fd b){
    return a.x>b.x||(a.x==b.x&&a.y>b.y);
}
void vk()
{
    memset(sum_x,0,sizeof(sum_x)); memset(sum_y,0,sizeof(sum_y));
    memset(cnt_x,0,sizeof(cnt_x)); memset(cnt_y,0,sizeof(cnt_y));
    for(int i=1;i<=n;++i)
    {
        int x=a[i].x,y=a[i].y;
        sum_x[x]=(sum_x[x]+(long long)abs(y-last_x[x])*cnt_x[x])%1000000007;
        ++cnt_x[x]; last_x[x]=y;
        sum_y[y]=(sum_y[y]+(long long)abs(x-last_y[y])*cnt_y[y])%1000000007;
        ++cnt_y[y]; last_y[y]=x;
        ans=(ans+sum_x[x]*sum_y[y])%1000000007;
    }
}
int main()
{
    cin >> n;
    for(int i=1;i<=n;++i){
        cin >> a[i].x >> a[i].y;
        a[i].x+=10000;
        a[i].y+=10000;
    } 
    sort(a+1,a+n+1,cmp1); vk();
    sort(a+1,a+n+1,cmp2); vk();
    sort(a+1,a+n+1,cmp3); vk();
    sort(a+1,a+n+1,cmp4); vk();
    printf("%lld\n",ans);
    return 0;
}