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

struct Point
{
	int id;
	int x;
	int y;
};

int use_sqrt1 = 0;
//расстояние между двумя точками в D^2
long double get_distance_between_Points(struct Point* p1, struct Point* p2)
{
#ifdef _DEBUG
		use_sqrt1++;
#endif
	long double dx = p1->x - p2->x;
	long double dy = p1->y - p2->y;
	return sqrt(dx*dx + dy*dy);
}

//вес графа. на входе адрес графа, количество точек, стартовая позиция
long double get_weight_graph(struct Point* p, int num, int s)
{
	long double res = 0;
	for (int i = 0; i < num; ++i)
	{
		res += get_distance_between_Points(p + i, p + s);
	}
	return res;
}

//Попытка провести интернет
bool try_connect_to_WEB(struct Point* p, int num, struct Point* center, long double money, int cast)
{
	long double res;
	int i = 0;
	do
	{
		res = get_weight_graph(p, num, i) + get_distance_between_Points(p + i, center);
		i += 1;
	} while (res*cast > money && i < num);
	return res*cast <= money;
}

// ***********************************************************************************************
#define POINT_COUNT 5000
#include <time.h>

long double* cache = NULL;
int use_sqrt2 = 0;
int use_cache = 0;

//расстояние между двумя точками в D^2
long double get_distance_between_Points2(struct Point* p1, struct Point* p2)
{
	long double res = cache[p1->id * POINT_COUNT + p2->id];
	if(res == 0) {
		long double dx = p1->x - p2->x;
		long double dy = p1->y - p2->y;
		res = sqrt(dx*dx + dy*dy);
		cache[p2->id * POINT_COUNT + p1->id] = res;
#ifdef _DEBUG
		use_sqrt2++;
	}  else {
		use_cache++;
#endif
	}
	return res;
}

//вес графа. на входе адрес графа, количество точек, стартовая позиция
long double get_weight_graph2(struct Point* p, int num, int s)
{
	long double res = 0;
	for (int i = 0; i < num; ++i)
	{
		res += get_distance_between_Points2(p + i, p + s);
	}
	return res;
}


bool try_connect_to_WEB2(struct Point* p, int num, struct Point* center, long double money, int cast)
{
	long double res;
	int i = 0;
	do
	{
		res = get_weight_graph2(p, num, i) + get_distance_between_Points(p + i, center);
		i += 1;
	} while (res*cast > money && i < num);
	return res*cast <= money;
}


int main(int argc, char** argv)
{
	srand((int)time(NULL));
	struct Point p[POINT_COUNT];
	int num = POINT_COUNT;
	int cast = 1;
	long double money = POINT_COUNT * 300;
	for(int i = 0; i < POINT_COUNT; i++) {
		p[i].id = i;
		p[i].x = rand() % 1000;
		p[i].y = rand() % 1000;
	}
	struct Point center;
	center.id = POINT_COUNT;
	center.x = rand() % 1000;
	center.y = rand() % 1000;

	// вариант SashaMercury
	clock_t time1 = clock();
	bool res1 = try_connect_to_WEB(p,num,&center,money,cast);

	// вариант кэшем
	clock_t time2 = clock();
	cache = (long double*)calloc(POINT_COUNT * POINT_COUNT, sizeof(long double));
	bool res2 = try_connect_to_WEB2(p,num,&center,money,cast);

	clock_t time3 = clock();
	printf("Res 1 %s time %d  sqrt=%d\n", res1 ? "YES" : "NO", time2 - time1, use_sqrt1);
	printf("Res 2 %s time %d  cache=%d sqrt=%d\n", res2 ? "YES" : "NO", time3 - time2, use_cache, use_sqrt2);

	system("pause");
	return 0;
}