Cross the yard without getting wet

Here is the question:

There is a house with a backyard which is square bounded by coordinates (0,0) in the southwest to (1000,1000) in the northeast. In this yard there are a number of water sprinklers placed to keep the lawn soaked in the middle of the summer. However, it might or might not be possible to cross the yard without getting soaked and without leaving the yard?

Input The input starts with a line containing an integer 1≤n≤1000, the number of water sprinklers. A line follows for each sprinkler, containing three integers: the (x,y)(x,y) location of the sprinkler (0≤x,y,≤10000) and its range r (1≤r≤1000). The sprinklers will soak anybody passing strictly within the range of the sprinkler (i.e., within distance strictly less than r).

The house is located on the west side (x=0) and a path is needed to the east side of the yard (x=1000).

Output If you can find a path through the yard, output four real numbers, separated by spaces, rounded to two digits after the decimal place. These should be the coordinates at which you may enter and leave the yard, respectively. If you can enter and leave at several places, give the results with the highest y. If there is no way to get through the yard without getting soaked, print a line containing “IMPOSSIBLE”.

Sample Input

3
500 500 499
0 0 999
1000 1000 200

Sample output

0.00 1000.00 1000.00 800.00

Here is my thought process:

• Define circle objects with x,y,r and write a function to determine if a given point is wet or not(inside the circle or not) on the circumference is not wet btw.

  class circle {
     int h;
     int k;
     int r;
  
  public:
     circle();
     circle(int h, int k, int r){
         this->h = h;
         this->k = k;
         this->r = r;
     };
  
     bool iswet(pair<int,int>* p){
         if (pow(this->r - 0.001, 2)  > (pow(p->first - this->h, 2) + 
             pow(p->second - this->k, 2) ) ) {
             return true; 
         }     
         else
           return false;
     };
  

• Then implement a depth first search, prioritizing to go up and right whenever possible.

However since circles are not guaranteed to be pass on integer coordinates an the result is expected in floats with double precision (xxx.xx). So if we keep everything in integers the grid suddenly becomes 100,000 x 100,000 which is way too big. Also the time limit is 1 sec. So I thought ok lets stick to 1000x1000 and work with floats instead. Loop over int coordinates and whenever I hit a sprinkle just snap in the perimeter of the circle since we are safe in the perimeter. But in that case could not figure out how DFS work.

Here is the latest trial

#include <iostream>
#include <cmath>
#include <string>
#include <vector>
#include <deque>
#include <utility>
#include <unordered_set>
#include <iomanip>

using namespace std;

const int MAXY = 1e3;
const int MAXX = 1e3;
const int MINY = 0;
const int MINX = 0;

struct pair_hash {
    inline std::size_t operator()(const std::pair<int,int> & v) const {
        return v.first*31+v.second;
    }
};


class circle {
    int h;
    int k;
    int r;

  public:

    circle();
    circle(int h, int k, int r){
        this->h = h;
        this->k = k;
        this->r = r;
    };
    bool iswet(pair<float,float>* p){
        if (pow(this->r - 0.001, 2)  > (pow(p->first - this->h, 2) + pow(p->second - this->k, 2) ) ) {
            this->closest_pair(p);
            return true; 
        }
        else
            return false;
    };

    void closest_pair(pair<float,float>* p){
            float vx = p->first - this->h;
            float vy = p->second - this->k; 
            float magv = sqrt(vx * vx + vy * vy); 
            p->first = this->h + vx / magv * this->r;
            p->second = this->k + vy / magv * this->r;
    }
};


static bool test_sprinkles(vector<circle> &sprinkles, pair<float,float>* p){


    for (int k = 0; k < sprinkles.size(); k++)
        if (sprinkles[k].iswet(p)) return false; 
    return true;

}

int main(){
    int n; // number of sprinkles 
    while (cin >> n){
        vector<circle> sprinkles_array;
        sprinkles_array.reserve(n);
        int h, k, r;
        while (n--){
          cin >> h >> k >> r;
          sprinkles_array.push_back(circle(h, k, r));
        }/* code */

        pair<float,float> enter = make_pair(0, MAXY);
        deque<pair<float,float>> mystack; 
        mystack.push_back(enter);
        pair<float,float>* cp;
        bool found = false;
        unordered_set<pair<float, float>, pair_hash> visited;


        while (!mystack.empty()){
            cp = &mystack.back(); 
            if (cp->first == MAXX) {
                found = true;
                break;
            }
            visited.insert(*cp);

            if (cp->second > MAXY || cp->second < MINY || cp ->first < MINX ) {
                visited.insert(*cp);
                mystack.pop_back();
                continue;
            }
            if (!test_sprinkles(sprinkles_array,cp))  {      
                continue;
            }
            pair<int,int> newpair = make_pair(cp->first, cp->second + 1);
            if (visited.find(newpair) == visited.end())  {      
                mystack.push_back(newpair);
                continue;
            }
            else visited.insert(newpair);

            newpair = make_pair(cp->first + 1 , cp->second);
            if (visited.find(newpair) == visited.end())  {      
                mystack.push_back(newpair);
                continue;
            }
            else visited.insert(newpair);

            newpair = make_pair(cp->first, cp->second - 1);
            if (visited.find(newpair) == visited.end())  {      
                mystack.push_back(newpair);
                continue;
            }
            else visited.insert(newpair);

            newpair = make_pair(cp->first - 1, cp->second);
            if (visited.find(newpair) == visited.end())  {      
                mystack.push_back(newpair);
                continue;
            }
            else visited.insert(newpair);

            mystack.pop_back();
        }
        cout << setprecision(2);
        cout << fixed;
        if (found){
            double xin = mystack.front().first;
            double yin = mystack.front().second;
            pair <float, float>  p = mystack.back();
            p.second++;
            for (int k = 0; k < sprinkles_array.size(); k++)
                if (sprinkles_array[k].iswet(&p)) break;   
            double xout = p.first;
            double yout = p.second;


            cout << xin << " " << yin << " " << xout << " " << yout << endl;
        }
        else
        {
            cout << "IMPOSSIBLE" << endl;
        }

    }


}