리스트의 이차원 배열

/- 프로그램 명 : 단위 크기의 정사각형에 있는 N개의 점에 대한 순서쌍 중 몇 개가 d 보다 작은 거리를 갖는지 알아보기 *-

#include <math.h>

#include <stdio.h>

#include <stdlib.h>

#include "Point.h"

/- Point.h

typedef struct Point{

float x, y;

} Point;

*-

typedef struct node *link;

struct node{

point p;

link next;

};

link **grid; // 격자

int G;

float d; // 거리

int cnt = 0; // count

gridinsert(float x, float y)

{

int i, j;

link s;

int X = x*G + 1, Y = y*G + 1; // 삽입할 데이터의 범위(격자위치)를 찾는다.

link t = (link*) calloc(1, sizeof(*t));

t->p.x = x, t->p.y = y;

for(i = X-1; i <= X+1; i++)

for(j = Y-1; j <= Y+1; j++)

for(s = grid[i][j]; s != NULL; s = s->next)

// d 거리 이내일 경우 개수를 더한다.

if(distance(s->p, t->p) < d)

cnt++;

// 데이터를 격자 범위에다 삽입한다.

t->next = grid[X][Y], grid[X][Y] = t;

}

link **malloc2d(int r, int c) // 이차원 calloc(malloc)

{

int i;

link **t = (link**) calloc(r, sizeof(*t));

for(i=0; i<r; i++)

t[i] = (link*) calloc(c, sizeof(*t[i]));

return t;

}

int main(void)

{

int i, j, N;

scanf("%d %f", &N, &d);

G = 1/d, grid = malloc2d(G+3, G+3);

// grid 생성, G 는 격자 범위를 나타내는 수

for(i=0; i < G+3; i++)

for(j=0; j < G+3; j++)

grid[i][j] = NULL;

for(i=0; i < N; i++)

gridinsert(randFloat(), randFloat());

// 데이터 삽입 randFloat 함수는 return 1.0 * rand()/RAND_MAX; 한다

printf("%d edges shorter than %f\n", cnt, d);

return 0;

}