Problem:

有N盆花，2个喷泉，它们都在不同的位置，
喷泉的浇灌覆盖半径分别为r1和r2，
输入花和喷泉的位置，求出保证所有的花都被喷泉覆盖时最小的r1^2+r2^2。

Answer:

要想所求结果最小，喷泉的边界上必定有某个点，
所以遍历所有以到喷泉1的距离为喷泉边界的情况，
结果就是所有情况中r1^2+r2^2的最小值。
C++：

#include
#include
#include
#include
define x first
define y second
define dis(x1,y1,x2,y2) ((x2-x1)(x2-x1)+(y2-y1)(y2-y1))
using namespace std;

typedef long long ll;

const int maxn = 2016;

const ll MIN = 0;

const ll MAX = 0xefefefefefefefe;

vector<pair<ll,ll> > d(maxn);

int n;

pair<int,ll> p1,p2;

int main(){

//ifstream cin("in");

cin>>n>>p1.x>>p1.y>>p2.x>>p2.y;

for(int i=1;i<=n;++i){

ll tx,ty;

cin>>tx>>ty;

d[i].first = dis(p1.x,p1.y,tx,ty);

d[i].second = dis(p2.x,p2.y,ty);

}

d[0].first = d[0].second = 0;     //注意1：喷泉1的覆盖面积为0的情况

ll res=MAX,r1,r2;

for(int i=0;i<=n;++i){

r1 = d[i].first;

r2 = MIN;

for(int j=1;j<=n;++j){

if(d[j].first>=r1&&j!=i){

r2 = max(r2,d[j].second);

}

}

res = min(res,r1+r2);

}

if(n==1) res = min(d[1].first,d[1].second);

cout<<res<<endl;

}

（编辑：李大同）

【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容!