网上商城建设网站定制开发,制作书签,做抢单软件的网站,域名申请好后 如何建设网站题目链接#xff1a; http://acm.hust.edu.cn/vjudge/problem/307216Froggy FordTime Limit: 3000MS题意 青蛙过河#xff0c;河中有若干个石头#xff0c;现在你可以加一个石头#xff0c;使得青蛙从左岸跳到右岸的最大跳跃距离最小。 题解 把左岸和右岸作为两个虚节点 http://acm.hust.edu.cn/vjudge/problem/307216Froggy FordTime Limit: 3000MS 题意 青蛙过河河中有若干个石头现在你可以加一个石头使得青蛙从左岸跳到右岸的最大跳跃距离最小。 题解 把左岸和右岸作为两个虚节点用kruskal的思路处理出每个点到左岸需要跳跃的最大距离st[i]最优情况下和每个点到右岸的最大距离ed[i]然后枚举两个点在这两个点的中点放一个石头得到mamax(st[i],ed[j],dis(i,j)/2)如果这个值比答案更优就更新答案同时记录新放的石头的坐标。 代码 #includemap
#includecmath
#includequeue
#includevector
#includecstdio
#includestring
#includecstring
#includeiostream
#includealgorithm
using namespace std;
#define X first
#define Y second
#define mkp make_pair
#define lson (o1)
#define rson ((o1)|1)
#define mid (l(r-l)/2)
#define sz() size()
#define pb(v) push_back(v)
#define all(o) (o).begin(),(o).end()
#define clr(a,v) memset(a,v,sizeof(a))
#define bug(a) cout#a aendl
#define rep(i,a,b) for(int ia;i(b);i)typedef long long LL;
typedef vectorint VI;
typedef pairint,int PII;
typedef vectorpairint,int VPII;const int INF0x3f3f3f3f;
const LL INFL9e18;
const double eps1e-8;const int maxn1111;LL w,n;pairLL,LL pt[maxn];LL dis(LL x1,LL y1,LL x2,LL y2){return (x1-x2)*(x1-x2)(y1-y2)*(y1-y2);
}struct Edge{int u,v; LL w;Edge(int u,int v,LL w):u(u),v(v),w(w){}Edge(){}bool operator (const Edge tmp) const {return wtmp.w;}
}egs[maxn*maxn];int tot;
int fa[maxn];
int find(int x){return fa[x]fa[x]x?x:find(fa[x]);
}vectorint G[maxn];
int st[maxn],ed[maxn];void init(){clr(st,-1);clr(ed,-1);tot0;rep(i,0,maxn) fa[i]i;rep(i,0,maxn) G[i].push_back(i);
}int main() {freopen(froggy.in,r,stdin);freopen(froggy.out,w,stdout);init();scanf(%I64d%I64d,w,n);rep(i,1,n1) scanf(%I64d%I64d,pt[i].X,pt[i].Y);rep(i,1,n1){egs[tot]Edge(0,i,pt[i].X*pt[i].X);}rep(i,1,n1){egs[tot]Edge(i,n1,(w-pt[i].X)*(w-pt[i].X)); }rep(i,1,n1){rep(j,i1,n1){egs[tot]Edge(i,j,dis(pt[i].X,pt[i].Y,pt[j].X,pt[j].Y));}}egs[tot]Edge(0,n1,w*w);egs[tot]Edge(0,0,0);egs[tot]Edge(n1,n1,0);sort(egs,egstot);rep(i,0,tot){int uegs[i].u,vegs[i].v;if(u0v0){st[0]i; continue;}if(un1vn1){ed[n1]i; continue;}int pufind(u);int pvfind(v);if(pu!pv){if(find(0)pu){rep(j,0,G[pv].size()){int ttG[pv][j];st[tt]i;}}else if(find(0)pv){rep(j,0,G[pu].size()){int ttG[pu][j];st[tt]i;}}if(find(n1)pu){rep(j,0,G[pv].size()){int ttG[pv][j];ed[tt]i;}}else if(find(n1)pv){rep(j,0,G[pu].size()){int ttG[pu][j];ed[tt]i;}}fa[pv]pu;while(G[pv].size()0){G[pu].push_back(G[pv][G[pv].sz()-1]);G[pv].pop_back();}}}int ans_i0,ans_j0;double mi9000000000000000000;rep(i,0,n2){rep(j,0,n2){if(ij) continue;double tmpmax(egs[st[i]].w,egs[ed[j]].w);int tii,tjj;if(titj) swap(ti,tj);if(ti0tjn1){tmpmax(tmp,w*w*1.0/4);}else if(ti0){tmpmax(tmp,pt[tj].X*pt[tj].X*1.0/4);}else if(tjn1){tmpmax(tmp,(w-pt[ti].X)*(w-pt[ti].X)*1.0/4);}else{tmpmax(tmp,dis(pt[i].X,pt[i].Y,pt[j].X,pt[j].Y)*1.0/4);}if(tmpmi){mitmp;ans_ii; ans_jj;}}}double ans_x0,ans_y0;if(ans_ians_j) swap(ans_i,ans_j);if(ans_i0ans_jn1){ans_xw*1.0/2;ans_y0;}else if(ans_i0){ans_xpt[ans_j].X*1.0/2;ans_ypt[ans_j].Y;}else if(ans_jn1){ans_x(wpt[ans_i].X)*1.0/2;ans_ypt[ans_i].Y;}else{ans_x(pt[ans_i].Xpt[ans_j].X)*1.0/2;ans_y(pt[ans_i].Ypt[ans_j].Y)*1.0/2; }printf(%.3lf %.3lf\n,ans_x,ans_y);return 0;
} 转载于:https://www.cnblogs.com/fenice/p/5769356.html
