1 条题解
-
0
首先我们看到这个题
发现符合条件的三角形一共有4种

然后我们对于这样一种情况算一下答案

化简后答案可得:
所以说我们对于每一个点,即可从上下左右四个方向算出来前缀和,然后统计答案
(代码自己写吧我写的很shit)
#include<algorithm> #include<iostream> #include<cstring> #include<cstdio> #include<map> #define MAXN 20005 #define int long long using namespace std; bool Test_MLE_start; const int N=1e5+10; const int mod=1e9+7; int T=1,n,ans=0; int prey[MAXN],prex[MAXN],cntx[MAXN],cnty[MAXN],lstx[MAXN],lsty[MAXN]; struct node{ int x,y; }a[N]; bool Test_MLE_end; inline int reads(){ char c=getchar(); int sum=0,f=1; while(!isdigit(c)){ if(c=='-') f=-1; c=getchar(); } while(isdigit(c)){ sum=(sum<<3)+(sum<<1)+(c-'0'); c=getchar(); } return sum*f; } inline void files(){ freopen("std.in","r",stdin); freopen("std.out","w",stdout); } bool cmp1(node a,node b){return a.x==b.x?a.y<b.y:a.x<b.x;} bool cmp2(node a,node b){return a.x==b.x?a.y>b.y:a.x<b.x;} bool cmp3(node a,node b){return a.x==b.x?a.y<b.y:a.x>b.x;} bool cmp4(node a,node b){return a.x==b.x?a.y>b.y:a.x>b.x;} void clr(){ memset(prex,0,sizeof(prex)); memset(prey,0,sizeof(prey)); memset(cntx,0,sizeof(cntx)); memset(cnty,0,sizeof(cnty)); } signed main(){ // printf("%lf Mb\n",(&Test_MLE_end-&Test_MLE_start-1)/1024.0/1024.0); // files(); // T=reads(); while(T--){ n=reads(); for(int i=1;i<=n;i++){ a[i].x=reads(),a[i].y=reads(); a[i].x+=10000,a[i].y+=10000; } sort(a+1,a+n+1,cmp1); for(int i=1;i<=n;i++){ int x=a[i].x,y=a[i].y; prex[x]=(prex[x]+abs(y-lstx[x])*cntx[x])%mod; cntx[x]++; lstx[x]=y; prey[y]=(prey[y]+abs(x-lsty[y])*cnty[y])%mod; cnty[y]++; lsty[y]=x; ans=(ans+prex[x]*prey[y])%mod; } sort(a+1,a+n+1,cmp2); clr(); for(int i=1;i<=n;i++){ int x=a[i].x,y=a[i].y; prex[x]=(prex[x]+abs(y-lstx[x])*cntx[x])%mod; cntx[x]++; lstx[x]=y; prey[y]=(prey[y]+abs(x-lsty[y])*cnty[y])%mod; cnty[y]++; lsty[y]=x; ans=(ans+prex[x]*prey[y])%mod; } sort(a+1,a+n+1,cmp3); clr(); for(int i=1;i<=n;i++){ int x=a[i].x,y=a[i].y; prex[x]=(prex[x]+abs(y-lstx[x])*cntx[x])%mod; cntx[x]++; lstx[x]=y; prey[y]=(prey[y]+abs(x-lsty[y])*cnty[y])%mod; cnty[y]++; lsty[y]=x; ans=(ans+prex[x]*prey[y])%mod; } sort(a+1,a+n+1,cmp4); clr(); for(int i=1;i<=n;i++){ int x=a[i].x,y=a[i].y; prex[x]=(prex[x]+abs(y-lstx[x])*cntx[x])%mod; cntx[x]++; lstx[x]=y; prey[y]=(prey[y]+abs(x-lsty[y])*cnty[y])%mod; cnty[y]++; lsty[y]=x; ans=(ans+prex[x]*prey[y])%mod; } printf("%lld\n",ans); } return 0; }
- 1
信息
- ID
- 56
- 时间
- 1000ms
- 内存
- 256MiB
- 难度
- 7
- 标签
- (无)
- 递交数
- 18
- 已通过
- 10
- 上传者