Algorithms

Member 4194593 wrote:

Even comparing the smallest distance between any of the stars in all of the grid boxes may miss the case where a star in one grid box is immediately adjacent to another star in another grid box

{X<small>avg</small>, Y<small>avg</small>}

// VanillaConsole.cpp : Defines the entry point for the console application.
//
 
#include "stdafx.h"
#include <iostream>
#include <ostream>
#include <iterator>	// For 'ostream_iterator'.
#include <algorithm>	// For 'copy'.
#include <numeric>		// For 'accumulate'.
using namespace std;
 
// Structure to represent a point.
struct point
{
	point()
		: x(0), y(0) {}
	point(double x, double y)
		: x(x), y(y) {}
 
	double x;
	double y;
};
 
// Add two points together.
point operator+(const point &lhs, const point &rhs)
{
	return point(lhs.x+rhs.x, lhs.y+rhs.y);
}
 
// Divide a point by a number.
point operator/(const point &lhs, double rhs)
{
	return point(lhs.x/rhs, lhs.y/rhs);
}
 
// Output a point.
ostream& operator<<(ostream &os, const point &pt)
{
	os << "(" << pt.x << ", " << pt.y << ")";
	return os;
}
 
int main(int argc, char* argv[])
{
	// Our collection of points.
	const point pts[] =
	{
		point(1.0, 2.0),
		point(2.0, 1.0),
		point(3.0, 3.0),
		point(4.0, 4.0),
		point(-1.0, 3.0)
	};
	const point *pEnd = pts + sizeof(pts)/sizeof(pts[0]);
 
	// Output the points to the console.
	ostream_iterator<point> osi(cout, "\n");
	copy(pts, pEnd, osi);
	cout << endl;
 
	// Now calculate the closest point.
	point pt;
	pt = accumulate(pts, pEnd, pt);
	pt = pt/(sizeof(pts)/sizeof(pts[0]));
 
	// Output the result.
	cout << "Closest point is " << pt << endl;
 
	return 0;
}