首页 > 代码库 > 【HDOJ】4932 Miaomiao's Geometry
【HDOJ】4932 Miaomiao's Geometry
递归检测。因为dis数组开的不够大,各种wa。写了个数据发生器,果断发现错误,改完就过了。
1 #include <cstdio> 2 #include <cstring> 3 #include <iostream> 4 #include <algorithm> 5 6 using namespace std; 7 8 #define MAXN 55 9 10 int n;11 double a[MAXN], dis[MAXN*2];12 char visit[MAXN]; // 0: false, 1: left, 2:right13 14 bool dfs(int x, double l) {15 if (x == n-1)16 return true;17 if (x == 0) {18 visit[x] = 2;19 return dfs(x+1, l);20 }21 if (visit[x-1] == 2) {22 if (a[x-1]+l <= a[x]) {23 visit[x] = 2;24 if ( dfs(x+1, l) )25 return true;26 } else if (a[x]+l <= a[x+1]) {27 visit[x] = 1;28 return dfs(x+1, l);29 }30 return false;31 } else {32 if (a[x-1]+2*l <= a[x] || a[x-1]+l==a[x]) {33 visit[x] = 2;34 if ( dfs(x+1, l) )35 return true;36 } else if (a[x]+l <= a[x+1]) {37 visit[x] = 1;38 return dfs(x+1, l);39 }40 return false;41 }42 }43 44 int main() {45 //FILE *fout = fopen("data", "w");46 int case_n, m;47 int i;48 49 scanf("%d", &case_n);50 while (case_n--) {51 scanf("%d", &n);52 for (i=0; i<n; ++i)53 scanf("%lf", &a[i]);54 sort(a, a+n);55 for (m=0, i=1; i<n; ++i) {56 dis[m++] = a[i] - a[i-1];57 dis[m++] = (a[i] - a[i-1])/2;58 }59 sort(dis, dis+m);60 dis[m] = 0.0f;61 for (i=m-1; i>=0; --i) {62 if (dis[i] != dis[i+1]) {63 memset(visit, 0, sizeof(visit));64 if ( dfs(0, dis[i]) )65 break;66 }67 }68 printf("%.3lf\n", dis[i]);69 //fprintf(fout, "%.3lf\n", dis[i]);70 }71 72 return 0;73 }
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。