P6149 [USACO20FEB] Triangles S

题目描述

Farmer John 想要给他的奶牛们建造一个三角形牧场。

有 $N$（$3\le N\le 10^5$）个栅栏柱子分别位于农场的二维平面上不同的点 $(X_1,Y_1)\dots (X_N,Y_N)$。他可以选择其中三个点组成三角形牧场，只要三角形有一条边与 $x$ 轴平行或重合，且有另一条边与 $y$ 轴平行或重合。

FJ 可以组成的所有可能的牧场的面积之和等于多少？

输入格式

第一行包含 $N$。

以下 $N$ 行每行包含两个整数 $X_i$ 和 $Y_i$，均在范围 $-10^4\dots 10^4$ 之内，描述一个栅栏柱子的位置。

输出格式

由于面积之和不一定为整数且可能非常大，输出面积之和的两倍模 $10^9+7$ 的余数。

输入输出样例 #1

输入 #1

4
0 0
0 1
1 0
1 2

输出 #1

3

说明/提示

样例解释：

栅栏木桩 ($0,0$)、($1,0$) 和 ($1,2$) 组成了一个面积为 $1$ 的三角形，($0,0$)、($1,0$) 和 ($0,1$) 组成了一个面积为 $0.5$ 的三角形。所以答案为 $2\times (1+0.5)=3$。

子任务：

• 测试点 $2$ 满足 $N=200$。
• 测试点 $3$-$4$ 满足 $N\le 5000$。
• 测试点 $5$-$10$ 没有额外限制。

C++实现

#include<cstdio>
#include<algorithm>
#include<cstring>
#define N 100005
#define rep(i,a,b) for(int i=a;i<=b;i++)
using namespace std;
int n;
struct node{
	int x,y;
	bool operator<(const node o)const{
		if(x^o.x)return x<o.x;
		return y<o.y;
	}
}a[N];
typedef long long ll;
ll ans=0;const ll P = 1000000007LL;const int bas = 10007;
ll sum[N],cnt[N];
void solve(){
	sort(a+1,a+n+1);
	memset(sum,0,sizeof(sum));
	memset(cnt,0,sizeof(cnt));
	ll now = 0,tot = 0 ;
	rep( i , 1 , n ){
		if(a[i].x != a[i-1].x )now = 0 ,tot = 0 ;
		ans=(ans + ( a[i].x * cnt[a[i].y + bas] - sum[ a[i].y + bas ] )
		    % P * ( a[i].y * tot - now ) % P ) % P;
		tot++;now=(now+a[i].y)%P;
		cnt[a[i].y+bas]++;
		sum[a[i].y+bas]=(a[i].x+sum[a[i].y+bas])%P;
	}
}
void rev(){
	rep(i,1,n){
		int x=a[i].x,y=a[i].y;
		a[i].x=y;a[i].y=-x;
	}
}
int main(){
	scanf("%d",&n);
	rep(i,1,n)scanf("%d%d",&a[i].x,&a[i].y);
	rep(i,0,3){
		solve();rev();
	}
	printf("%lld\n",ans);
	return 0;
}

后续

接下来我会不断用C++来实现信奥比赛中的算法题、GESP考级编程题实现、白名单赛事考题实现，记录日常的编程生活、比赛心得，感兴趣的请关注，我后续将继续分享相关内容