Problem
I’m doing this problem, but for the test case I just get 1, instead of 3.
I’ve tried implementing the comp_size() method several different ways, and this seems to be the most logical. However, the program still isn’t working and I suspect it may be related to that method.
Here is my code:
#include <fstream>
#include <vector>
#include <algorithm>
#include <cmath>
using namespace std;
int n;
struct Cow
{
int x; int y; int power;
};
Cow cows[203];
vector<int> in_range[203];
bool visited[203];
double distance(Cow a, Cow b)
{
int x1 = a.x, y1 = a.y, x2 = b.x, y2 = b.y;
int xdiff = x1-x2, ydiff = y1-y2;
double dist = pow(xdiff, 2) + pow(ydiff, 2);
return dist;
}
void dfs(int node)
{
visited[node] = true;
for (auto x : in_range[node])
{
if (!visited[x]) dfs(x);
}
}
int comp_size(int node)
{
//finds the number of cows that can be reached from the cow node
int cnt = 0;
dfs(node);
for (int i = 0; i < 201; i++)
{
if (visited[i]) cnt++;
}
fill(visited, visited+202, false);
return cnt;
}
int main()
{
fill(visited, visited+203, false);
ifstream cin("moocast.in"); ofstream cout("moocast.out");
cin >> n;
for (int i = 0; i < n; i++)
{
cin >> cows[i].x >> cows[i].y >> cows[i].power;
}
for (int i = 0; i < n; i++)
{
for (int j = 0; i < n; i++)
{
if (i == j) continue;
Cow cow = cows[i], cow2 = cows[j];
if (distance(cow, cow2) <= pow(cow.power,2)) in_range[i].push_back(j);
}
}
int highest = 0;
for (int i = 0; i < n; i++)
{
highest = max(highest, comp_size(i));
}
cout << highest;
}