algorithm - Partition Frisbees C++ -

we have set f of n frisbee's in 2d. want partition f 2 subsets f1, , f2 no 2 frisbee's intersect in each respective subset. our function takes in input so: (x_j, y_j) centre of j-th frisbee, , rad_j radius of j-th frisbee. output should s_0 s_1 ... s_n-1, s_j = 1 if j-th frisbee in f1 , s_i = 2 if j-th frisbee in f2. if cannot partition f, return 0. ideally, algo should computed in o(n^2) time.

i figured should use type type of matrix representation of graph, don't think need need construct graph, think bfs/dfs useful, i'm stuck on how elegantly in o(n^2). coding in c++ way.

you on right track graph search. here's c++11, o(v^2), depth first search solution uses o(v+e) space.

the dfs o(v+e) in time, generating adjacency lists o(v^2) obvious way.

#include <iostream> #include <vector> #include <cmath>  using namespace std;  struct frisbee {   double x;   double y;   double radius; };  int dfs(const vector< vector<int> > &adj, vector<int> &p, int last_ind, int curr_ind) {   if (p[curr_ind])                   // node painted   {      if (p[last_ind] == p[curr_ind])  // painted same color neighbor -> failure       return 0;      return 1;                        // painting compatible   }    // node not yet painted    p[curr_ind] = (1 == p[last_ind] ? 2 : 1);        // paint opposite color neighbor    (int j = 0; j < adj[curr_ind].size(); ++j)     if (!dfs(adj, p, curr_ind, adj[curr_ind][j]))  // dfs on neighbors       return 0;    return 1; }  int partition(const vector<frisbee> &f, vector<int> &p) {   // compute adjacency lists    vector< vector<int> > adj(f.size());    p.resize(f.size());    (int = 0; < f.size(); ++i)   {     p[i] = 0;      (int j = + 1; j < f.size(); ++j)     {       double dist = sqrt((f[i].x - f[j].x) * (f[i].x - f[j].x) + (f[i].y - f[j].y) * (f[i].y - f[j].y));        if (dist < f[i].radius + f[j].radius)       {         adj[i].push_back(j);         adj[j].push_back(i);       }     }   }    // find starting points dfs    (int = 0; < f.size(); ++i)     if (0 == p[i])                       // node not yet painted     {             p[i] = 1;                          // arbitrarily choose initial color        (int j = 0; j < adj[i].size(); ++j)         if (!dfs(adj, p, i, adj[i][j]))  // dfs on neighbors           return 0;     }    return 1; }  int main(int argc, char **argv) {   vector<frisbee> f = { { 1.0, 1.0, 1.0 }, { 2.0, 2.0, 1.0 }, { -1.0, -1.0, 1.0 }, { -2.0, -2.0, 1.0 }, { 5.0, 5.0, 1.0 }, { -5.0, 5.0, 1.0 } };   vector<int>     p;    if (partition(f, p))   {     (size_t = 0; < f.size(); ++i)       cout << p[i] << " ";      cout << endl;   }   else     cout << "no partition possible!" << endl;    f.push_back({ 1.5, 1.5, 1.0 });  // add 3-way intersection    if (partition(f, p))   {     (size_t = 0; < f.size(); ++i)       cout << p[i] << " ";      cout << endl;   }   else     cout << "no partition possible!" << endl;     return 0; } 

here's output (of 2 partitions on different sets of frisbee's):

1 2 1 2 1 1  no partition possible!