Posted on 2012-08-14 21:39
hoshelly 閱讀(326)
評論(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;
}