CTUOPEN2017GoNorthwest!///简单公式

OStack程序员社区-中国程序员成长平台 › 门户 › 编程› Go›Go教程

原作者: [db:作者] 来自: [db:来源] 收藏邀请

题目大意：

给定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;
}