Program C : Jarak Terdekat antara 2 Titik (Closest Pair)

Algoritma Closest Pair digunakan ketika kita ingin mencari dua titik yang berdekatan pada n titik. Contoh permasalahan closest pair pada kehidupan sehari-hari adalah mencari jarak terdekat antar 2 pesawat atau lebih yang memiliki kemungkinan bertabrakan. Berikut adalah algoritma closest pair :

//Input: A list P of n(n≥ 2) points P_1 (x_1,y_1 )^,..., P_n (x_n,y_n )^

//Output: The distance between the closest pair of points

  d ←∞

  for i ← 1 to n − 1 do

  for j ← i + 1 to n do

  d ← min(d, sqrt((x_i− x_j )^2+(y_i− y_j )^2) //sqrt is square root

  return d

//end

dan untuk Source Code nya (Bahasa C) adalah sebagai berikut :

#include <stdio.h>

#include <math.h>

int main(){

int i,j,n;

float dmin,x[40],y[40],x1,x2,y1,y2;

printf("masukan banyaknya titik : ");

scanf("%d",&n);

for(i=1;i<=n;i++){

printf("\n");

printf("masukan kordinat x titik ke-%d : ",i);

scanf("%f",&x[i]);

printf("masukan kordinat y titik ke-%d : ",i);

scanf("%f",&y[i]);

}

dmin=999999999; //karena tdk ada fungsi infinite jadi pakai nilai terbesar

for (i=1;i<=n-1;i++){

for (j=i+1;j<=n;j++){

if(sqrt((x[i]-x[i+1])*(x[i]-x[i+1])+(y[i]-y[i+1])*(y[i]-y[i+1]))<=dmin){

  dmin=sqrt((x[i]-x[i+1])*(x[i]-x[i+1])+(y[i]-y[i+1])*(y[i]-y[i+1]));

  x1=x[i];

  x2=x[i+1];

  y1=y[i];

  y2=y[i+1];

  }   

}

}

printf("\n\njarak terdekat adalah antara titik (%.0f,%.0f) dengan (%.0f,%.0f) \nyaitu sejauh %.2f",x1,y1,x2,y2,dmin);

}

Eksekusi Program :

Sekian postingan kali ini, semoga bermanfaat.