首页 > 代码库 > 【UVA】10012 - How Big Is It?(暴力)
【UVA】10012 - How Big Is It?(暴力)
利用DFS枚举所有排列,之后每次添加一个圆的时候,他的位置是和前面所有已经添加圆的相切的位置的最大。
14383635 | 10012 | How Big Is It? | Accepted | C++ | 0.086 | 2014-10-20 11:07:33 |
#include<cstdio> #include<cmath> #include<cstring> #include<algorithm> using namespace std; typedef double Dou; #define FOR(i,n) for(int i = 0; i < n; i ++) const int maxn = 10; int n,vis[maxn]; Dou ans,r[maxn]; struct POS{ //圆心位置就是(x,r) Dou x,r; //横坐标,半径 }pos[maxn]; Dou check(int cur,int k){ Dou ret = r[k]; FOR(i,cur){ Dou a = pos[i].r + r[k]; Dou b = pos[i].r - r[k]; Dou c = sqrt(a * a - b * b); ret = max(ret,pos[i].x + c); } pos[cur].x = ret; pos[cur].r = r[k]; return ret + r[k]; } void dfs(int cur,double L){ if(ans != -1 && L > ans) return; if(cur == n){ Dou ret; for(int i = 0; i < cur; i++){ if(i == 0) ret = pos[i].x + pos[i].r; else ret = max(ret,pos[i].x + pos[i].r); } ans = (ans == -1) ? ret : min(ans,ret); return; } FOR(i,n) if(!vis[i]){ vis[i] = 1; dfs(cur + 1,check(cur,i)); vis[i] = 0; } return; } int main(){ int T; scanf("%d",&T); while(T--){ scanf("%d",&n); ans = -1; memset(vis,0,sizeof(vis)); FOR(i,n) scanf("%lf",&r[i]); dfs(0,0.0); printf("%.3f\n",ans); } return 0; }
【UVA】10012 - How Big Is It?(暴力)
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。