首页 > 代码库 > poj3347Kadj Squares

poj3347Kadj Squares

2024-07-15 04:02:03   222人阅读

链接

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

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

用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

 

 1 #include <iostream> 2 #include<cstdio> 3 #include<cstring> 4 #include<algorithm> 5 #include<stdlib.h> 6 #include<vector> 7 #include<cmath> 8 #include<queue> 9 #include<set>10 using namespace std;11 #define N 5512 #define LL long long13 #define INF 0xfffffff14 const double eps = 1e-8;15 const double pi = acos(-1.0);16 const double inf = ~0u>>2;17 int o[N],a[N],lef[N],rig[N];18 19 int main()20 {21     int i,j,n;22     while(scanf("%d",&n)&&n)23     {24         memset(o,0,sizeof(o));25         for(i = 1; i <= n ;i++)26         {27             scanf("%d",&a[i]);28         }29         lef[1] = 0;30         rig[1] = 2*a[1];31         for(i = 2; i <= n ;i++)32         {33             lef[i] = 0;34             for(j = 1; j < i ; j++)35             lef[i] = max(lef[i],rig[j]-abs(a[i]-a[j]));36             rig[i] = lef[i]+2*a[i];37             //cout<<lef[i]<<" "<<rig[i]<<endl;38         }39         int g = 0;40         for(i = 1; i <= n ;i++)41         {42             int le = lef[i],re = rig[i];43             for(j = 1; j < i ; j++)44             {45                 le = max(le,rig[j]);46             }47             for(j = i+1 ; j <= n; j++)48             re = min(re,lef[j]);49             //cout<<le<<" "<<re<<endl;50             if(re>le)51             o[++g] = i;52         }53         for(i = 1; i < g ; i++)54         printf("%d ",o[i]);55         printf("%d\n",o[g]);56     }57     return 0;58 }
View Code

 


联系
我们