首页 > 代码库 > 【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 }