SRM443 CirclesCountry

Circles Country is a country that contains several circular-shaped districts. Some districts may be situated inside other districts, but their borders do not intersect or touch. Qatam is a resident of Circles Country. When he travels between two locations, he always tries to cross the fewest number of district borders as possible because crossing borders is usually a laborious task.

Imagine Circles Country as an infinite plane. You are given int[]s X, Y and R, where (X[i], Y[i]) are the coordinates of the i-th district’s center and R[i] is its radius. Qatam is currently at point (x1,y1) and he needs to get to point (x2,y2). Neither of these points lies on a district border. Return the minimal number of district borders he must cross to get to his destination.

#include <vector>
using namespace std;

class CirclesCountry {
    public:
        int leastBorders(vector <int> X, vector <int> Y, vector <int>R, int x1, int y1, int x2, int y2){
            int num = 0;

            for (int i = 0; i < X.size(); i++){
                if (inside(X[i], Y[i], x1, y1, R[i]) != (inside(X[i], Y[i], x2, y2, R[i])))
                    num++;
            }

            bool inside(int x1, int y1, int x2, int y2, int r){
                return (x1 - x2) * (x1 - x2) + (y1 - y2) * (y1 - y2) <= r * r;
            }
        }
};

(x1 – x2) * (x1 – x2) + (y1 – y2) * (y1 – y2) <= r * r;が x1y1とx2y2で正しくなければ境界線が1つとなる。すなわち、insideでは片方が円の中にあり、片方が円の外に点があるかどうかを判定している。コーディングというより問題の理解力の方が求められるか...