poj3347Kadj Squares

链接

这题其实与几何没太大关系，还不错的题目。

参考吴永辉的算法设计书。

用lefi、rigi分别表示正方形在x轴上的投影。

为了避免用小数，把边长都扩大sqrt(2)倍，这样lef1 = 0，rig1 = 2*a1;

lefi = max{rigj-abs(ai-aj)}

rigi = lefi+2*ai;

求出各个正方形的投影之后，这题就好做了。用le和re表示正方形的可见区间。

le = max(rigj,lefi) j <i

re = min(lefj,rigi) j>i

 #include <iostream>

 #include<cstdio>

 #include<cstring>

 #include<algorithm>

 #include<stdlib.h>

 #include<vector>

 #include<cmath>

 #include<queue>

 #include<set>

 using namespace std;

 #define N 55

 #define LL long long

 #define INF 0xfffffff

 const double eps = 1e-;

 const double pi = acos(-1.0);

 const double inf = ~0u>>;

 int o[N],a[N],lef[N],rig[N];

 int main()

 {

     int i,j,n;

     while(scanf("%d",&n)&&n)

     {

         memset(o,,sizeof(o));

         for(i = ; i <= n ;i++)

         {

             scanf("%d",&a[i]);

         }

         lef[] = ;

         rig[] = *a[];

         for(i = ; i <= n ;i++)

         {

             lef[i] = ;

             for(j = ; j < i ; j++)

             lef[i] = max(lef[i],rig[j]-abs(a[i]-a[j]));

             rig[i] = lef[i]+*a[i];

             //cout<<lef[i]<<" "<<rig[i]<<endl;

         }

         int g = ;

         for(i = ; i <= n ;i++)

         {

             int le = lef[i],re = rig[i];

             for(j = ; j < i ; j++)

             {

                 le = max(le,rig[j]);

             }

             for(j = i+ ; j <= n; j++)

             re = min(re,lef[j]);

             //cout<<le<<" "<<re<<endl;

             if(re>le)

             o[++g] = i;

         }

         for(i = ; i < g ; i++)

         printf("%d ",o[i]);

         printf("%d\n",o[g]);

     }

     return ;

 }