 |
I would not expect you to figure this out on a test. However, it shows the power of structuring problems with graphs. We'll see more of that later in the semester.
As always, let's wrap our heads around the problem with the examples. Here's a drawing of example #0, where there is one sensor at (50,2) with a threshold of 87.
|
I'm only showing the relevant part of the room. I've drawn two circles around the sensor. The first has a radius of 1, which means that when the intruder's noise level is 87, the sensor can detect the intruder when the intruder is at or within that circle. The second has a radius of 2, which means that when the intruder's noise level is at 348, the sensor can detect the intruder when the intruder is at or within that circle. This is because (A/d2) ≥ 87.
It should be pretty clear that so long as the intruder's noise level is less than 348, he can bypass the sensor. Therefore, the answer is any value that is less than 348 by 10-9 or less. The answer that the example gives is 347.99999999999994, which certainly fits the bill.
Let's try example #2:
 |
I've drawn circles where the radius equals 5, and therefore it can detect noises where A ≥ 25, and where the radius equals 49, and therefore it can detect noises where A ≥ 2401. It should be clear from the picture that so long as A < 2401, the intruder can get through. Therefore, the answer is any value that is less than 2401 by 10-9 or less.
One more picture. Let's look at example 2, when A = 1538:
 |
Well, I can see why 1538 is the crossing point. But how to turn this into a solution? And what does this have to do with graph theory?
Here's a better example. Let's move one sensor from (11,10) to (18,15), and another from (62,25) to (62,30), and keep A at 1538:
 |
It should be clear from this picture that at this value of A, the intruder cannot pass from one door to another. Those three sensors and the walls make it impossible. Hopefully this example gives you a clue about turning the problem into a graph.
You insert an edge between two sensors if their circles intersect for that value of A. You also insert an edge between a sensor and a "wall" node if the sensor's circle intersects the wall. If the edge of the circle intersects a door, then you put edges to both wall nodes. As an example, here's the graph of that last set of sensors when A = 1538:
 |
If there is a path in this graph from the "Left" node to the "Right" node, then the intruder cannot pass.
So, our first piece of code is to write a procedure called TestA(), which takes a value of A, creates the graph and prints it out. We read in A before calling it to test it. It's in Alarmed-1.cpp, and below. It calculates the radius of a sensor as: r = sqrt(A/T). It then checks the distance between every pair of sensors, and if that distance is less than the sum of the two radii, then it creates an edge in the graph. Finally, it checks for intersecting with the "Left" node and "Right" node. That check is a bit complex -- I've put comments in there so you can see each case: Alarmed-1.cpp
#include <string>
#include <cmath>
#include <vector>
#include <iostream>
#include <cstdio>
#include <cstdlib>
using namespace std;
class Vertex {
public:
int visited;
vector <int> adj;
};
class Alarmed {
public:
int TestA(double A);
vector <double> X;
vector <double> Y;
vector <double> T;
vector <Vertex> V;
double noise(vector <int> x, vector <int> y, vector <int> threshold);
};
int Alarmed::TestA(double A)
{
int lw, rw;
int i, j;
vector <double> Radius;
double d;
int intersect;
V.clear();
V.resize(X.size()+2);
lw = X.size();
rw = X.size()+1;
for (i = 0; i < X.size(); i++) {
Radius.push_back(sqrt(A/T[i]));
printf("Radius of %d: %lf\n", i, Radius[i]);
}
cout << endl;
for (i = 0; i < X.size(); i++) {
for (j = 0; j < i; j++) {
d = sqrt(((X[i] - X[j])*(X[i]-X[j]))+
((Y[i] - Y[j])*(Y[i]-Y[j])));
printf("Distance between %d and %d: %lf (%lf)\n", i, j, d, Radius[i]+Radius[j]);
if (d <= Radius[i]+Radius[j]) {
V[i].adj.push_back(j);
V[j].adj.push_back(i);
}
}
/* Check for edge to "Left" */
intersect = 0;
if (X[i] <= Radius[i]) intersect = 1; /* Intersect with left wall */
/* Intersect with top or bottom wall, left: */
if (X[i] <= 50 && (Y[i] <= Radius[i] || Y[i]+Radius[i] >= 100)) intersect = 1;
if (X[i] > 50) { /* Check to see if either door is in the circle */
d = sqrt((X[i]-50)*(X[i]-50)+(Y[i]*Y[i]));
if (d <= Radius[i]) intersect = 1;
d = sqrt((X[i]-50)*(X[i]-50)+((100-Y[i])*(100-Y[i])));
if (d <= Radius[i]) intersect = 1;
}
if (intersect) {
V[lw].adj.push_back(i);
V[i].adj.push_back(lw);
}
/* Check for edge to "Right" */
intersect = 0;
if ((100-X[i]) <= Radius[i]) intersect = 1;
if (X[i] >= 50 && (Y[i] <= Radius[i] || Y[i]+Radius[i] >= 100)) intersect = 1;
if (X[i] < 50) {
d = sqrt((50-X[i])*(50-X[i])+(Y[i]*Y[i]));
if (d <= Radius[i]) intersect = 1;
d = sqrt((50-X[i])*(50-X[i])+((100-Y[i])*(100-Y[i])));
if (d <= Radius[i]) intersect = 1;
}
if (intersect) {
V[rw].adj.push_back(i);
V[i].adj.push_back(rw);
}
}
for (i = 0; i < V.size(); i++) {
printf("%d:", i);
for (j = 0; j < V[i].adj.size(); j++) printf(" %d", V[i].adj[j]);
printf("\n");
}
}
double Alarmed::noise(vector <int> x, vector <int> y, vector <int> threshold)
{
int i;
double A;
for (i = 0; i < x.size(); i++) {
X.push_back(x[i]);
Y.push_back(y[i]);
T.push_back(threshold[i]);
}
cout << "Enter A: ";
cin >> A;
i = TestA(A);
return 0;
}
|
We compile and run it, and the graphs look as they should. In example 0, there are no edges when A=87, but there are edges from the sensor to the left and right nodes with A=348. When A is slightly smaller, there are no edges:
UNIX> cp Alarmed-1.cpp Alarmed.cpp UNIX> g++ Alarmed-Main.cpp UNIX> a.out 0 Enter A: 87 Radius of 0: 1.000000 0: 1: 2: 0 UNIX> a.out 0 Enter A: 348 Radius of 0: 2.000000 0: 1 2 1: 0 2: 0 0 UNIX> a.out 0 Enter A: 347.9999999 Radius of 0: 2.000000 0: 1: 2: 0In example 1, we test the two circles in the drawing -- A=25 and A=2401. In both cases, there are edges from a sensor to a wall, but in the second, there is also an edge between sensors:
UNIX> a.out 1 Enter A: 25 Radius of 0: 5.000000 Radius of 1: 5.000000 Distance between 1 and 0: 98.000000 (10.000000) 0: 2 1: 3 2: 0 3: 1 0 UNIX> a.out 1 Enter A: 2401 Radius of 0: 49.000000 Radius of 1: 49.000000 Distance between 1 and 0: 98.000000 (98.000000) 0: 2 1 1: 0 3 2: 0 3: 1 0 UNIX>
The code is in Alarmed-2.cpp. I'm only including the DFS and the final testing in TestA:
void Alarmed::DFS(int n)
{
int i;
if (V[n].visited) return;
V[n].visited = 1;
for (i = 0; i < V[n].adj.size(); i++) DFS(V[n].adj[i]);
}
int Alarmed::TestA(double A)
{
....
for (i = 0; i < V.size(); i++) V[i].visited = 0;
DFS(lw);
return (V[rw].visited);
}
|
When we run it, it works as anticipated:
UNIX> cp Alarmed-2.cpp Alarmed.cpp UNIX> g++ Alarmed-Main.cpp UNIX> a.out 0 Enter A: 87 0 0 UNIX> a.out 0 Enter A: 348 1 0 UNIX> a.out 0 Enter A: 347.9999999999 0 0 UNIX> a.out 1 Enter A: 2401 1 0 UNIX> a.out 1 Enter A: 2400.9999999 0 0 UNIX>The last piece of the puzzle is to find the right value of A. I'm going to do it by binary search. I'll start with A equal to one and I'll keep multiplying it by 10 until I find a value where the intruder cannot pass. Call that value higha. And start with lowa equal to zero. Then iterate the following:
double Alarmed::noise(vector <int> x, vector <int> y, vector <int> threshold)
{
int i;
double lowa, higha, mida;
for (i = 0; i < x.size(); i++) {
X.push_back(x[i]);
Y.push_back(y[i]);
T.push_back(threshold[i]);
}
for (higha = 1; !TestA(higha) ; higha *= 10) ;
lowa = 0;
while(higha-lowa >= 0.000000001) {
mida = (higha+lowa)/2.0;
if (mida == higha || mida == lowa) return lowa;
if (TestA(mida)) {
higha = mida;
} else {
lowa = mida;
}
}
printf("Final answer: %.11lf\n", lowa);
return lowa;
}
|
Test it out:
UNIX> cp Alarmed-3.cpp Alarmed.cpp UNIX> g++ Alarmed-Main.cpp UNIX> a.out 0 Final answer: 347.99999999996 348 UNIX> a.out 1 Final answer: 2400.99999999984 2401 UNIX> a.out 2 Final answer: 1537.99999999990 1538 UNIX> a.out 3 Final answer: 3295.57178787468 3295.57 UNIX>Time to submit!