题目大意:

给定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+;
const int mod=1e9+;
const double eps=1e-; LL n;
map<LL,LL>mp1,mp2; int main()
{
while(~scanf("%lld",&n)) {
mp1.clear(); mp2.clear();
inc(i,,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-);
for(it=mp2.begin();it!=mp2.end();it++)
ans+=it->second*(it->second-);
printf("%lf\n",ans/sum);
} return ;
}

最新文章

  1. DOM对象 与 jQuery对象 之间的相互装换
  2. Dijkstra堆优化与SPFA模板
  3. 45. Jump Game II
  4. Openfire 代码部署报错: Variable references non-existent resource:${workspace_loc:openfire_src}
  5. Android 仿QQ微信开场导航以及登陆界面
  6. 基于集合成工控机Ubuntu系统安装分区详解
  7. Java IO详解(五)------包装流
  8. Java &lt;clinit&gt; &amp; &lt;init&gt;
  9. spring security 4 filter 顺序及作用
  10. 完美的js运动框架
  11. Python-类的绑定方法与非绑定方法
  12. A1119. Pre- and Post-order Traversals
  13. 5. 支持向量机(SVM)软间隔
  14. Docker实战(五)之端口映射与容器互联
  15. Python Machine Learning: Scikit-Learn Tutorial
  16. 03 Editor plugins and IDEs 编辑器插件和 ide
  17. 关于线上js报错问题的思考
  18. Maven学习(十二)-----Maven POM
  19. linux系统更改当前主机名
  20. POJ2739 Sum of Consecutive Prime Numbers 确定某个数以内的所有素数

热门文章

  1. box-shadow 制作单边阴影效果,不影响其它边的效果
  2. SQL语句优化方式--进阶篇
  3. JAVA 实现Jacob语音播报
  4. 【知识强化】第六章 查找 6.4 散列(Hash)表
  5. sql查询静态数据
  6. gevent协程之猴子补丁带来的坑
  7. Codeforces 360D Levko and Sets (数论好题)
  8. hibernate简单连接mysql数据库配置
  9. 【leetcode】976. Largest Perimeter Triangle
  10. 【leetcode】908. Smallest Range I