Human inspector versus programmer (was: Algorithm for determining if any circles overlap)

For each display:

If distance(A.center, B.center) < (A.radius+B.radius)
   the circles overlap.

      

        
        
        
      

    

In your case, it seems like each circle has the same radius, but I allowed the possibility of each circle having a different radius, just in case.

As for how long it takes to come up with this, it's a little tricky to say for sure - less time than it took to load the full description page. Then I had to read some things to confirm that the main problem was that it was from the title ...

Edit: If you had a lot of circles, it might be worth doing some sorting to eliminate unnecessary overlap tests, but assuming only 30 circles per map, which probably isn't worth it - you'll need a truly ancient computer to do this it will take a whole second.

Sorry, had to leave a little to take the kids to the hockey game. Anyway, although I haven't tested it, here's what I'll be doing for a C ++ program in about 10-12 minutes (I needed to call there, so I don't have the exact time):

#include <vector>
#include <math.h>
#include <iostream>

struct point { 
    int id, x, y;
};

std::istream &operator>>(std::istream &is, point &p) { 
    return is >> p.id >> p.x >> p.y;
}

typedef std::vector<point> map;

double dist(point const &a, point const &b) { 
    double x=a.x-b.x;
    double y=a.y-b.y;
    return sqrt(x*x+y*y);
}

int main() { 
    std::vector<map> maps(24);
    int mapID;
    while (std::cin>> mapID) {
        point temp;
        std::cin >> temp;
        maps[mapID].push_back(temp);
    }

    for (int i=0; i<maps.size(); i++)
        for (int j=0; j<maps[j].size(); j++) 
            for (int k=j; k<maps[j].size(); k++) 
                if (dist(maps[i][j], maps[i][k]) < 60)
                    std::cout 
                        << "map " << i << "\t" 
                        << maps[i][j].id 
                        << " overlaps with " 
                        << maps[i][k].id << "\n";
    return 0;
}

      

        
        
        
      

    

I haven't actually tested this, so it might take 5 to 10 minutes (or something in that order) to make sure it works correctly, but I wouldn't expect anything much longer. Anyway, I would expect one person to finish within an hour. If you're used to something like AWK or Perl, I'd rather finish a little more quickly - although to be honest it's trivial enough that it basically boils down to shortening typing ...