Closest Pair of Points

/*** Divide & Conquer – Closest Pair of Points

We are given an array of n points in the plane, and the problem is to find out the closest pair of points in the array. This problem arises in a number of applications. For example, in air-traffic control, you may want to monitor planes that come too close together, since this may indicate a possible collision. Recall the following formula for distance between two points p and q.

       Euclidean Distance = sqrt((p1.x – p2.x)^2 + (p1.y – p2.y)^2);

***/

#include<iostream>

#include<cmath>

#include <vector>

#include<algorithm>

#include<utility>

#include<limits>

using namespace std;

struct point {

       int x;

       int y;

};

bool sX (point p1, point p2);

bool sY (point p1, point p2);

class closestPair {

public:

       closestPair(int (*a)[2], int n);

       ~closestPair(){ }

       void getClosestpair(int begin, int end);

       double minDist;

      

private:

       vector<point> points;

//     int minDist;

       pair<point, point> closest;

       double distance(point p1, point p2);

       void crossDist(int vline, int begin, int end);

};

closestPair::closestPair(int (*a)[2], int n) {

       point p;

       points.clear();

       for(int i = 0; i < n; i++) {

              p.x = a[i][0];

              p.y = a[i][1];

              points.push_back(p);

       }

       sort(points.begin(), points.end(), sX);

       minDist = INT_MAX;

}

void closestPair::getClosestpair(int begin, int end) {

       int mid;

       double dist;

       int vline;

       if(begin == end) return;

       if(begin == end + 1) {

              dist = distance(points[begin], points[end]);

              if(minDist > dist) {

                     minDist = dist;

                     closest = make_pair(points[begin], points[end]);

              }

       }

       mid = (begin + end) / 2;

       vline = points[mid].x;

       getClosestpair(begin, mid);

       getClosestpair(mid+1, end);

       crossDist(vline, begin, end);

}

bool sX (point p1, point p2) {

       return (p1.x < p2.x);

}

bool sY (point p1, point p2) {

       return (p1.y < p2.y);

}

double closestPair::distance(point p1, point p2) {

       return sqrt((p1.x – p2.x)*(p1.x – p2.x) + (p1.y – p2.y)*(p1.y – p2.y));

}

void closestPair::crossDist(int vline, int begin, int end) {

       int xd;

       double dist;

       vector<point> left, right;

       for(int i = begin; i <= end; i++) {

              xd = points[i].x – vline;

              if(xd > 0 && abs(xd) < minDist) {

                     right.push_back(points[i]);

              }

              if(xd <= 0 && abs(xd) < minDist) {

                     left.push_back(points[i]);

              }

       }

       sort(left.begin(), left.end(), sY);

       sort(right.begin(), right.end(), sY);

       for(int i = 0; i < left.size(); i++) {

              for(int j = 0; j < right.size(); j++) {

                     if(j > i+7) break;

                     dist = distance(left[i], right[j]);

                     if(dist < minDist) {

                           minDist = dist;

                           closest = make_pair(points[i], points[j]);

                     }

              }

       }            

}

int main()

{

       int a[][2] = {{2, 3}, {12, 30}, {40, 50}, {5, 1}, {12, 10}, {3, 4}};

       int n = sizeof(a) / sizeof(a[0]);

       closestPair cp(a, n);

       cp.getClosestpair(0, n-1);

       cout<< “min = “<< cp.minDist<<endl;

       return 0;

}

Min in Array

/***

Find the minimum element in a sorted and rotated array

July 2, 2013

A sorted array is rotated at some unknown point, find the minimum element in it.

Following solution assumes that all elements are distinct.

Examples

Input: {5, 6, 1, 2, 3, 4}

Output: 1

Input: {1, 2, 3, 4}

Output: 1

Input: {2, 1}

Output: 1

***/

#include

using namespace std;

int minInArray(int *a, int low, int high)

 {

       int mid, l,r;

       if(low >= high)

              return a[high];

       // the mid of low and high

       mid=(high + low)/2 ;

      

       if(a[mid] < a[mid-1])

              return a[mid];

       l=minInArray(a,low,mid);

       r=minInArray(a,mid+1,high);

 

       if(l<r)

              return l;

       return r;

}

void main() {

       int min;

       int a[] = {5, 6, 1, 2, 2, 3, 3, 4};

       int sz = sizeof(a) / sizeof(int);

       min = minInArray(a, 0, sz-1);

       cout << min<<endl;

}

Big Difference

/***

There is an integer array consisting positive and negative integers. Find maximum

positive difference S defined as:

S = a[i] – a[j] where i>j

and

S > 0

***/

#include

using namespace std;

int bigDiff(int *a, int sz) {

       int min = 0;

       int dif = 0;

       for(int i = 0; i<sz; i++) {

              if (a[i] < 0)

              {

                     if (min > a[i]) min = a[i];

              } else {

                     if (dif < a[i] – min) dif = a[i] – min;

              }

       }

       return dif;

}

void main() {

       int a[] = {-3, -2, 11, -5, 3, 6, 8};

       int sz = sizeof(a) / sizeof(int);

       int diff = bigDiff(a, sz);

       cout<<diff<<endl;

}