CTU OPEN 2017 Go Northwest! /// 简单公式
2024-09-04 05:20:24
题目大意:
给定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 ;
}
最新文章
- DOM对象 与 jQuery对象 之间的相互装换
- Dijkstra堆优化与SPFA模板
- 45. Jump Game II
- Openfire 代码部署报错: Variable references non-existent resource:${workspace_loc:openfire_src}
- Android 仿QQ微信开场导航以及登陆界面
- 基于集合成工控机Ubuntu系统安装分区详解
- Java IO详解(五)------包装流
- Java <;clinit>; &; <;init>;
- spring security 4 filter 顺序及作用
- 完美的js运动框架
- Python-类的绑定方法与非绑定方法
- A1119. Pre- and Post-order Traversals
- 5. 支持向量机(SVM)软间隔
- Docker实战(五)之端口映射与容器互联
- Python Machine Learning: Scikit-Learn Tutorial
- 03 Editor plugins and IDEs 编辑器插件和 ide
- 关于线上js报错问题的思考
- Maven学习(十二)-----Maven POM
- linux系统更改当前主机名
- POJ2739 Sum of Consecutive Prime Numbers 确定某个数以内的所有素数