比赛 USACO银组重赛hhh 评测结果 AAAAAAAAAA
题目名称 Triangles(Silver) 最终得分 100
用户昵称 梦那边的美好ET 运行时间 0.234 s
代码语言 C++ 内存使用 19.00 MiB
提交时间 2020-03-01 21:41:47
显示代码纯文本
#include<bits/stdc++.h>
#define maxn 300010
#define maxm 20010
#define LL long long 
using namespace std;
const LL mod=(LL)1000000007,add=(LL)10000;
int n;
struct node{
    LL x,y;
    bool operator<(const node &a1)const{
	    if(x==a1.x)return y<a1.y;
	    return x<a1.x;
	}
}a[maxn];
LL ans,su,sum,f[maxm],s[maxm],g[maxm],a1[maxm],a2[maxm];
void solve(int j){
    ans=(ans+(a1[a[j].y]*a[j].x-a2[a[j].y]+mod)%mod*sum)%mod;
	f[a[j].y]=((f[a[j].y]+(a[j].x-s[a[j].y])*g[a[j].y])%mod+mod)%mod;
	s[a[j].y]=a[j].x;g[a[j].y]=(g[a[j].y]+sum)%mod;ans=(ans+f[a[j].y])%mod;
	return;
}
int main(){
	freopen("usaco_Feb_triangles.in","r",stdin);
	freopen("usaco_Feb_triangles.out","w",stdout);
	scanf("%d",&n);
	for(int i=1;i<=n;i++)
	    scanf("%lld%lld",&a[i].x,&a[i].y),
	    a[i].x+=add,a[i].y+=add;
	sort(a+1,a+1+n);
	for(int l=1,r=0;l<=n;l=r+1){
		while(a[r+1].x==a[l].x&&r<=n)r++;
		su=(LL)(r-l);sum=(LL)0;
		for(int j=l;j<=r;j++)sum=(sum+a[j].y-a[l].y)%mod;
		solve(l);
		if(r>l)for(int j=l+1;j<=r;j++){
			sum=(sum-su*(a[j].y-a[j-1].y)%mod+mod)%mod;
			sum=(sum+(LL)(r-l+1-su)*(a[j].y-a[j-1].y)%mod+mod)%mod;
		    solve(j);su--;
		}
		for(int j=l;j<=r;j++)a1[a[j].y]++,a2[a[j].y]=(a2[a[j].y]+a[j].x)%mod;
	}
	printf("%lld\n",(ans%mod+mod)%mod);
	return 0;
}