NC220366. G分割
描述
保证所有直线不完全重叠。
输入描述
第一行输入两个数字n,m代表竖线的数量和横线的数量.
第二行输入n个数字,代表n条竖线的x坐标x[i].
第三行输入m个数字,代表m条横线的y坐标y[i].
输出描述
输出一个数字,表示答案。
示例1
输入:
3 2 1 2 3 1 2
输出:
4
说明:
可能形成三个矩形，面积分别为1，1，2，故总面积为4C++(clang++11) 解法, 执行用时: 83ms, 内存消耗: 3588K, 提交时间: 2021-03-30 15:23:22
#include<bits/stdc++.h>
using namespace std;
const int mod=1e9+7;
const int N=1e6;
long long m,n,p,q,a[N],b[N],i;
int main(){cin>>n>>m;for(i=1;i<=n;i++)cin>>a[i];for(i=1;i<=m;i++)cin>>b[i];sort(a+1,a+1+n);sort(b+1,b+1+m);for(i=1;i<n;i++) p=(p+(a[i+1]-a[i])*(i)*(n-i))%mod;for(i=1;i<m;i++) q=(q+(b[i+1]-b[i])*(i)*(m-i))%mod;cout<<(p*q)%mod;}