1 条题解

  • 0
    @ 2025-3-4 9:20:03

    首先我们看到这个题

    发现符合条件的三角形一共有4种

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

    化简后答案可得:

    (3c+2b+a)×(3f+2e+d)(3c+2b+a) \times (3f+2e+d)

    所以说我们对于每一个点,即可从上下左右四个方向算出来前缀和,然后统计答案

    (代码自己写吧我写的很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
    上传者