本文共 1446 字,大约阅读时间需要 4 分钟。
题目地址:
先二分半径。然后小于该半径的不能选,对这些不能选的点对进行加边。然后推断可行性就可以。
代码例如以下:
#include #include #include #include #include #include #include #include #include #include #include using namespace std;#define LL __int64const int INF=0x3f3f3f3f;const double eqs=1e-3;int head[410], cnt, top, ans, index;int dfn[410], low[410], instack[410], stak[410], belong[410];struct node{ int u, v, next;}edge[1000000];struct Point{ int x, y;}dian[10000];void add(int u, int v){ edge[cnt].v=v; edge[cnt].next=head[u]; head[u]=cnt++;}void tarjan(int u){ dfn[u]=low[u]=++index; instack[u]=1; stak[++top]=u; for(int i=head[u];i!=-1;i=edge[i].next) { int v=edge[i].v; if(!dfn[v]) { tarjan(v); low[u]=min(low[u],low[v]); } else if(instack[v]) { low[u]=min(low[u],dfn[v]); } } if(dfn[u]==low[u]) { ans++; while(1) { int v=stak[top--]; instack[v]=0; belong[v]=ans; if(u==v) break; } }}void init(){ memset(head,-1,sizeof(head)); cnt=0; memset(dfn,0,sizeof(dfn)); memset(instack,0,sizeof(instack)); top=ans=index=0;}double dist(Point x, Point y){ return sqrt((x.x-y.x)*(x.x-y.x)*1.0+(x.y-y.y)*(x.y-y.y));}int solve(double mid, int n){ int i, j; init(); for(i=0;i <<1;i++) { for(j=0;j eqs) { mid=(l+r)/2; //printf("%.2lf\n",mid); if(solve(mid, n)) { ans=mid; l=mid; } else r=mid; } printf("%.2lf\n",ans/2.0); } return 0;}
转载于:https://www.cnblogs.com/jzdwajue/p/6802710.html