题目大意:
给定n个点 求任选一对点连成的直线斜率为1或-1的概率
对于点(x1,y1) 和 点(x2,y2)
斜率 k=(y1-y2)/(x1-x2)
当k=1 则 (y1-y2)/(x1-x2)=1 -> y1-y2=x1-x2 -> y1-x1=y2-x2
当k=-1 则 (y1-y2)/(x1-x2)=-1 -> y1-y2=-(x1-x2) -> y1+x1=y2+x2
那么记录下所有点的 y-x 和 y+x
那么所有 y-x 相等的点即可凑成斜率为1的组合
若有n个这样的点 那么有 n*(n-1) 种组合
y+x同理 用map记录一下
符合要求的组合数 / 所有组合数 就得到概率
#include <bits/stdc++.h> using namespace std; #define LL long long #define INF 0x3f3f3f3f #define mem(i,j) memset(i,j,sizeof(i)) #define inc(i,l,r) for(int i=l;i<=r;i++) #define dec(i,r,l) for(int i=r;i>=l;i--) #define gcd(i,j) __gcd(i,j); const int N=2e5+5; const int mod=1e9+7; const double eps=1e-8; LL n; map<LL,LL>mp1,mp2; int main() { while(~scanf("%lld",&n)) { mp1.clear(); mp2.clear(); inc(i,1,n) { LL x,y; scanf("%lld%lld",&x,&y); mp1[y-x]++; mp2[x+y]++; } double sum=n*n, ans=0.0; map<LL,LL>::iterator it; for(it=mp1.begin();it!=mp1.end();it++) ans+=it->second*(it->second-1); for(it=mp2.begin();it!=mp2.end();it++) ans+=it->second*(it->second-1); printf("%lf\n",ans/sum); } return 0; }View Code