Posted on 2012-08-14 21:39
hoshelly 阅读(330)
评论(0) 编辑 收藏 引用 所属分类:
Programming 、
DS && Algorithm
编写程序，对于N个随机产生的单位正方形中的点，统计可以被长度小于d的直线连结的点对数。
程序如下：
typedef
struct{
float x;
float y; } point;
//定义点的数据类型
float distance(point,point);
//两点之间距离函数
float distance(point a,point b)
{
float dx= a.x - b.x, dy= a.y - b.y;
return sqrt(dx*dx + dy*dy);
}
//以上为头文件 Point.h 的内容
#include<stdio.h>
#include<stdlib.h>
#include<math.h>
#include "Point.h"
float randFloat()
{
return 1.0*rand()/RAND_MAX; }
//产生随机数的函数
int main()
{
float d,N;
int i,j,cnt=0;
scanf("%f%f",&d,&N);
//d为要求两点之间距离小于的长度，N为测试的点
point *a = (point *)malloc(
sizeof(point)*N);
//动态生成数据类型为point的数组a
for(i=0;i<N;i++)
{
a[i].x = randFloat(); a[i].y = randFloat();
}
for(i=0;i<N;i++)
for(j=i+1;j<N;j++)
if(distance(a[i],a[j])<d)
//如果两点之间的距离小于d，那么cnt加1
cnt++;
printf("%d edges shorter than %f\n",cnt,d);
//输出有多少条边的长度小于d
return 0;
}