1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170 171 172 173 174 175 176 177 178 179 180 181 182 183 184 185 186 187 188 189 190 191 192
|
#include <iostream>
#include <cmath>
#pragma warning (disable:4996)
using namespace std;
//closest pair of points
//so the idea is that i search for the min x coordinate of the bench and the min x coordinate of the lamp, because if i use a for cycle and compare bench[i]
//and lamp[i] there is no point in doing that
//so with this recursive func i find the closest x coordinates and then find the distance and say if the lamp lights the bench or not
void does_the_lapm_light_the_bench( int* array_x_benches, int* array_y_benches, int* array_x_lamps, int* array_y_lamps,
int* array_radius_lamps,int number_benches,int number_lamps)
{
if (number_benches > 0 && number_lamps > 0) {
int min_x_benches = array_x_benches[0];
int index_min_x_benches = 0;
for (size_t i = 0; i < number_benches; i++)
{
if (array_x_benches[i] <= min_x_benches)
{
min_x_benches = array_x_benches[i];
index_min_x_benches = i;
}
}
int min_x_lamps = array_x_lamps[0];
int index_min_x_lamps = 0;
for (size_t i = 0; i < number_lamps; i++)
{
if (array_x_lamps[i] <= min_x_lamps)
{
min_x_lamps = array_x_lamps[i];
index_min_x_lamps = i;
}
}
int distance = 0;
distance = sqrt(((array_x_benches[index_min_x_benches] - array_x_lamps[index_min_x_lamps]) *
(array_x_benches[index_min_x_benches] - array_x_lamps[index_min_x_lamps])) +
(array_y_benches[index_min_x_benches] - array_y_lamps[index_min_x_lamps]) *
(array_y_benches[index_min_x_benches] - array_y_lamps[index_min_x_lamps]));
if (distance > array_radius_lamps[index_min_x_lamps] || distance == array_radius_lamps[index_min_x_lamps])
{
cout << "The lamp does not light the bench" << endl;
cout << "The distance between the bench and the lamp is: " << distance << endl;
cout << "The bench is with coodinates: (" << array_x_benches[index_min_x_benches] << ", " << array_y_benches[index_min_x_benches] << ")" << endl;
cout << "The lamp is with coordinates: (" << array_x_lamps[index_min_x_lamps] << ", " << array_y_lamps[index_min_x_lamps] << "), the radius is: " <<
array_radius_lamps[index_min_x_lamps] << endl;
cout << endl;
}
else if (distance < array_radius_lamps[index_min_x_lamps] || (array_x_benches[index_min_x_benches] == array_x_lamps[index_min_x_lamps] &&
array_y_benches[index_min_x_benches] == array_y_lamps[index_min_x_lamps]))
{
cout << "The lamp lights the bench" << endl;
cout << "The distance between the bench and the lamp is: " << distance << endl;
cout << "The bench is with coodinates: (" << array_x_benches[index_min_x_benches] << ", " << array_y_benches[index_min_x_benches] << ")" << endl;
cout << "The lamp is with coordinates: (" << array_x_lamps[index_min_x_lamps] << ", " << array_y_lamps[index_min_x_lamps] << "), the radius is: " <<
array_radius_lamps[index_min_x_lamps] << endl;
cout << endl;
}
}
return does_the_lapm_light_the_bench(array_x_benches + 1, array_y_benches + 1, array_x_lamps + 1, array_y_lamps + 1, array_radius_lamps + 1, number_benches - 1,
number_lamps - 1);
}
void remove_useless_lamps(int* array_x_benches, int* array_y_benches, int* array_x_lamps, int* array_y_lamps, int* array_radius_lamps,
int number_benches, int number_lamps)
{
//we do the same thing but now the radius is the same for all the lamps
//the radius is the min radius of all of the lamps
//if the lamp does not light the bench we remove it
if (number_benches > 0 && number_lamps > 0) {
int min_x_benches = array_x_benches[0];
int index_min_x_benches = 0;
for (size_t i = 0; i < number_benches; i++)
{
if (array_x_benches[i] <= min_x_benches)
{
min_x_benches = array_x_benches[i];
index_min_x_benches = i;
}
}
int min_x_lamps = array_x_lamps[0];
int index_min_x_lamps = 0;
for (size_t i = 0; i < number_lamps; i++)
{
if (array_x_lamps[i] <= min_x_lamps)
{
min_x_lamps = array_x_lamps[i];
index_min_x_lamps = i;
}
}
int distance = 0;
distance = sqrt(((array_x_benches[index_min_x_benches] - array_x_lamps[index_min_x_lamps]) *
(array_x_benches[index_min_x_benches] - array_x_lamps[index_min_x_lamps])) +
(array_y_benches[index_min_x_benches] - array_y_lamps[index_min_x_lamps]) *
(array_y_benches[index_min_x_benches] - array_y_lamps[index_min_x_lamps]));
//checking which is the min radius
int min = array_radius_lamps[0];
for (size_t i = 0; i < number_lamps; i++)
{
if (array_radius_lamps[i] <= min)
{
min = array_radius_lamps[i];
}
}
if (distance > min || distance == min)
{
cout << "The lamp does not light the bench" << endl;
cout << "The distance between the bench and the lamp is: " << distance << endl;
cout << "The bench is with coodinates: (" << array_x_benches[index_min_x_benches] << ", " << array_y_benches[index_min_x_benches] << ")" << endl;
cout << "The lamp is with coordinates: (" << array_x_lamps[index_min_x_lamps] << ", " << array_y_lamps[index_min_x_lamps] << "), the radius is: " <<
array_radius_lamps[index_min_x_lamps] << endl;
cout << endl;
cout << "Removing the bench. " << endl;
swap(array_x_lamps[index_min_x_lamps], array_x_lamps[number_lamps]);
--number_lamps;
}
else if (distance < min || (array_x_benches[index_min_x_benches] == array_x_lamps[index_min_x_lamps] &&
array_y_benches[index_min_x_benches] == array_y_lamps[index_min_x_lamps]))
{
cout << "The lamp lights the bench" << endl;
cout << "The distance between the bench and the lamp is: " << distance << endl;
cout << "The bench is with coodinates: (" << array_x_benches[index_min_x_benches] << ", " << array_y_benches[index_min_x_benches] << ")" << endl;
cout << "The lamp is with coordinates: (" << array_x_lamps[index_min_x_lamps] << ", " << array_y_lamps[index_min_x_lamps] << "), the radius is: " <<
array_radius_lamps[index_min_x_lamps] << endl;
cout << endl;
}
return does_the_lapm_light_the_bench(array_x_benches + 1, array_y_benches + 1, array_x_lamps + 1, array_y_lamps + 1, array_radius_lamps + 1,
number_benches - 1, number_lamps - 1);
}
}
int main()
{
unsigned int number_benches = 0;
cout << "Please enter a valid number of benches: " << endl;
cin >> number_benches;
unsigned int number_lamps = 0;
cout << "Please enter a valid number of lamps: " << endl;
cin >> number_lamps;
//in an array we save the x and y coordinates
int* array_x_benches;
int* array_y_benches;
//in an array we save the x and y coordinates and then the radius
int* array_x_lamps;
int* array_y_lamps;
int* array_radius_lamps;
array_x_benches = new(nothrow)int[number_benches];
array_y_benches = new(nothrow)int[number_benches];
array_x_lamps = new(nothrow)int[number_lamps];
array_y_lamps = new(nothrow)int[number_lamps];
array_radius_lamps = new(nothrow)int[number_lamps];
cout << "Please enter all the x and y coordintes of the benches:/enter x then y/ " << endl;
for (size_t i = 0; i < number_benches; i++)
{
cin >> array_x_benches[i];
cin >> array_y_benches[i];
}
cout << "Please enter all the x and y coordinates and the radius of the lamp:/enter x, then y, then the raidus/ " << endl;
for (size_t i = 0; i < number_lamps; i++)
{
cin >> array_x_lamps[i];
cin >> array_y_lamps[i];
cin >> array_radius_lamps[i];
}
does_the_lapm_light_the_bench(array_x_benches, array_y_benches, array_x_lamps, array_y_lamps, array_radius_lamps, number_benches, number_lamps);
remove_useless_lamps(array_x_benches, array_y_benches, array_x_lamps, array_y_lamps, array_radius_lamps, number_benches, number_lamps);
cout << endl;
cout << "The number of the left lamps is: " << number_lamps << endl;
delete[]array_x_benches;
delete[]array_y_benches;
delete[]array_x_lamps;
delete[]array_y_lamps;
delete[]array_radius_lamps;
return 0;
}
|