P6149 [USACO20FEB] Triangles S题目描述Farmer John 想要给他的奶牛们建造一个三角形牧场。有N NN3 ≤ N ≤ 10 5 3\leq N\leq 10^53≤N≤105个栅栏柱子分别位于农场的二维平面上不同的点( X 1 , Y 1 ) … ( X N , Y N ) (X_1,Y_1)\ldots (X_N,Y_N)(X1​,Y1​)…(XN​,YN​)。他可以选择其中三个点组成三角形牧场只要三角形有一条边与x xx轴平行或重合且有另一条边与y yy轴平行或重合。FJ 可以组成的所有可能的牧场的面积之和等于多少输入格式第一行包含N NN。以下N NN行每行包含两个整数X i X_iXi​和Y i Y_iYi​均在范围− 10 4 … 10 4 −10^4\ldots 10^4−104…104之内描述一个栅栏柱子的位置。输出格式由于面积之和不一定为整数且可能非常大输出面积之和的两倍模10 9 7 10^971097的余数。输入输出样例 #1输入 #14 0 0 0 1 1 0 1 2输出 #13说明/提示样例解释栅栏木桩 (0 , 0 0,00,0)、(1 , 0 1,01,0) 和 (1 , 2 1,21,2) 组成了一个面积为1 11的三角形(0 , 0 0,00,0)、(1 , 0 1,01,0) 和 (0 , 1 0,10,1) 组成了一个面积为0.5 0.50.5的三角形。所以答案为2 × ( 1 0.5 ) 3 2\times (10.5)32×(10.5)3。子任务测试点2 22满足N 200 N200N200。测试点3 33-4 44满足N ≤ 5000 N\leq 5000N≤5000。测试点5 55-10 1010没有额外限制。C实现#includecstdio#includealgorithm#includecstring#defineN100005#definerep(i,a,b)for(intia;ib;i)usingnamespacestd;intn;structnode{intx,y;booloperator(constnode o)const{if(x^o.x)returnxo.x;returnyo.y;}}a[N];typedeflonglongll;ll ans0;constll P1000000007LL;constintbas10007;ll sum[N],cnt[N];voidsolve(){sort(a1,an1);memset(sum,0,sizeof(sum));memset(cnt,0,sizeof(cnt));ll now0,tot0;rep(i,1,n){if(a[i].x!a[i-1].x)now0,tot0;ans(ans(a[i].x*cnt[a[i].ybas]-sum[a[i].ybas])%P*(a[i].y*tot-now)%P)%P;tot;now(nowa[i].y)%P;cnt[a[i].ybas];sum[a[i].ybas](a[i].xsum[a[i].ybas])%P;}}voidrev(){rep(i,1,n){intxa[i].x,ya[i].y;a[i].xy;a[i].y-x;}}intmain(){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);return0;}后续接下来我会不断用C来实现信奥比赛中的算法题、GESP考级编程题实现、白名单赛事考题实现记录日常的编程生活、比赛心得感兴趣的请关注我后续将继续分享相关内容