c++ - 穿过院子而不被淋湿

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”.

样本输入

3
500 500 499
0 0 999
1000 1000 200

样本输出

0.00 1000.00 1000.00 800.00

以下是我的思考过程:

用 x,y,r 定义圆对象并编写一个函数来确定圆周上的给定点是否湿(在圆内或不在)是不湿的 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;
   };

然后实现深度优先搜索，尽可能优先向上和向右。

但是，由于不能保证在整数坐标上传递圆，因此预期结果为 double 浮点数 (xxx.xx)。因此，如果我们将所有内容都保留为整数，则网格会突然变成 100,000 x 100,000，这实在是太大了。时间限制也是1秒。
所以我认为可以让我们坚持 1000x1000 并使用浮点数代替。循环 int 坐标，每当我击中一个洒水器时，只需在圆的周长中对齐，因为我们在周长中是安全的。但在那种情况下无法弄清楚 DFS 是如何工作的。

这是最新的试用版

#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;
        }

    }


}

Answer 1

是的@JosephIreland 是对的。用分组相交(不接触)圆圈解决了这个问题。然后这些组具有最大和最小 y 坐标。如果它超过院子 miny 和 maxy，则该路被阻塞。

那么这些组也有x=0和x=1000线的上下交点。如果上部点大于码 maxy，则最大进入/退出点是下部进入点。

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

using namespace std;

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

struct circle {
    int h;
    int k;
    int r;
    float maxy;
    float miny;

    circle();
    circle(int h, int k, int r){
        this->h = h;
        this->k = k;
        this->r = r;
        this->miny = this->k - r;
        this->maxy = this->k + r;

    };
};



struct group {

    float maxy = -1;
    float miny = -1;
    vector<circle*> circles;
    float upper_endy = -1;
    float upper_starty = -1;
    float lower_endy = -1;
    float lower_starty = -1;



    void add_circle(circle& c){

        if ((c.maxy > this->maxy) || this->circles.empty() )  this->maxy = c.maxy;
        if ((c.miny < this->miny) || this->circles.empty() )  this->miny = c.miny;
        this->circles.push_back(&c);

        // find where it crosses x=minx and x= maxx
        float root = sqrt(pow(c.r, 2) - pow(MINX - c.h, 2));
        float y1 = root + c.k;
        float y2 = -root + c.k;

        if (y1 > this->upper_starty) this->upper_starty = y1;
        if (y2 > this->lower_starty) this->lower_starty = y2;

        root = sqrt(pow(c.r, 2) - pow(MAXX - c.h, 2));
        y1 = root + c.k;
        y2 = -root + c.k;
        if (y1 > this->upper_endy) this->upper_endy = y1;
        if (y2 > this->lower_endy) this->lower_endy = y2;

    };
    bool does_intersect(circle& c1){
        for(circle* c2 : circles){
            float dist = sqrt(pow(c1.h - c2->h,2)) +  sqrt(pow(c1.k - c2->k,2));
            (dist < (c1.r + c2->r)) ? true : false;
        };    
    };

};



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 */
        vector<group> groups;
        group newgroup;
        newgroup.add_circle(sprinkles_array[0]);
        groups.push_back(newgroup);

        for (int i = 1; i < sprinkles_array.size(); i++){ 
            bool no_group = true;
            for (group g:groups){
                if (g.does_intersect(sprinkles_array[i])){
                    g.add_circle(sprinkles_array[i]);
                    no_group = false;
                    break;
                }
            }
            if (no_group) {
                group newgroup;
                newgroup.add_circle(sprinkles_array[i]);
                groups.push_back(newgroup);
            }
        }

        float entery = MAXY;
        float exity = MAXY;
        bool found = true;
        for (group g : groups){
            if ((g.miny < MINY) && (g.maxy > MAXY)){
                found = false;
                break;
            }
            if (g.upper_starty > entery)
                entery = g.lower_starty;
            if (g.upper_endy > exity)
                exity = g.lower_endy;
        }

        cout << setprecision(2);
        cout << fixed;
        if (found){
            cout << float(MINX) << " " << entery << " " << float(MAXX) << " " << exity << endl;
        }
        else
        {
            cout << "IMPOSSIBLE" << endl;
        }

    }
}