# C language uses divide and conquer algorithm to solve the nearest point pair problem

## Nearest point to problem

There are many points in two-dimensional space. The coordinates of each point are (x, y). Find the coordinates and distances of the two closest points

## Solution

Consider two methods. The first method, violence solution, is easy to understand, but time complexity is high, when the number of points is large, it is difficult to run. The second method uses the idea of divide and conquer to solve the nearest point pair problem recursively.

### Violence law

```float baoli(Point points[], int length, Point &a, Point &b){
float min = 99999;
for(int i=0;i<length;i++){
for(int j=0;j<i;j++){
double temp = sqrt(pow(points[i].x-points[j].x,2)+pow(points[i].y-points[j].y,  2));
if(temp<min){
min = temp;
a = points[i];
b = points[j];
}
}
}
return min;
}
```

The idea of violence law is very simple, so there is no more explanation here

### Divide and conquer

The idea of divide and conquer method to solve the nearest problem is as follows:
First, the point pairs are sorted according to the size of the abscissa, which are divided into the left half and the right half. Recursively call the function to find the nearest point pair and the minimum distance d1, d2 of the left and right half, and then find the nearest point pair and the minimum distance of the min (D1, d2) neighborhood of the middle point. Compare with min (D1, d2), the smallest is taken.
The code is as follows.

```#include <stdio.h>
#include <math.h>

//Point is the structure of a point, x, y is the abscissa and ordinate
typedef struct Point{
float x;
float y;
}Point;
//The function of finding the distance between two points
float distance(Point a,Point b){
return sqrt((a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y));
}

//Quick row
int partition(Point a[],int begin,int end){
Point key = a[end];
int i = begin-1;
for(int j=begin;j<end;j++){
if(a[j].x<=key.x){
i++;
Point temp = a[i];
a[i] = a[j];
a[j] = temp;
}
}
i++;
a[end] = a[i];
a[i] = key;
return i;
}
void quiksort(Point a[],int begin,int end){
if(begin<end){
int middle = partition(a,begin,end);
quiksort(a,begin,middle-1);
quiksort(a,middle+1,end);
}
}
//Solving distance by divide and conquer method
float closest (Point* points,int n,Point &a, Point &b){
//Exit of recursive function, two points directly return distance, one point returns a maximum value
if(n==2){
a = points;
b = points;
return distance(a,b);
}
else if(n<2){
return 99999;
}
//Divide and conquer
else{
int n1 = n/2;
int n2 = n-n1;
float d1,d2,dis,mid;
Point points1 [n1];
Point points2 [n2];
Point a1,a2,b1,b2;
//Arrange point pairs according to x coordinate
quiksort(points,0,n-1);
mid = points[n1].x;
for(int i=0;i<n1;i++){
points1[i] = points[i];
}
for(int i=0;i<n2;i++){
points2[i] = points[i+n1];
}
//Left and right partitions
d1 = closest(points1,n1,a1,b1);
d2 = closest(points2,n2,a2,b2);
if(d1<=d2){
a = a1;
b = b1;
dis = distance(a,b);
}
else{
a = a2;
b = b2;
dis = distance(a,b);
}
//Middle area
Point points3[n];
int k = -1;
for(int i=0;i<n;i++){
if(abs(points[i].x-mid)<=dis){
points3[++k] = points[i];
}
}
for(int i=0;i<n;i++){
for(int j=i+1;j<i+7&&j<k;j++){
if(distance(points3[i],points3[j])<dis){
a = points3[i];
b = points3[j];
dis = distance(a,b);
}
}
}
return dis;

}
}
int main(void){
Point points = {{1.0,2.0},{1.1,6.2},{5.0,7.0},{15.0,12.5},{2.6,2.5},{5.9,4.6},{9.1,15.8}};
for(int i=0;i<7;i++){
printf("(%f,%f)\n",points[i].x,points[i].y);
}

Point a,b;
float dis = closest(points,7,a,b);
printf("distance%f，spot a(%f，%f)，spot b(%f，%f)",dis,a.x,a.y,b.x,b.y);
}
```

Added by sharapov on Thu, 05 Dec 2019 09:44:34 +0200