首页 > 代码库 > POJ 3347 Kadj Squares --扩展长度，几何，线段覆盖
POJ 3347 Kadj Squares --扩展长度，几何，线段覆盖
题意： n个正方形，边长为S[i]，斜45度按顺序平放在坐标轴上，尽量靠左，但是不能与前面任何一个相交，问从上往下看，哪些正方形是可见的。
解法： 我们先将边长扩张成sqrt(2)倍边长，这样的话就可以直接进行整数运算了。
然后分两步：
1.求出所有的b[i]
2.再进行区间覆盖判定
第一步：我们知道前面所有b[j]后，b[i]就是满足与前面任何一个都不相交的一个最左的位置。要满足于前面的都不相交又最靠左，我们就有： b[i] = max(b[i],b[j]+2*min(S[i],S[j]))， 根据下图，推一下就能得出。
第二步： 将所有正方形的L,R已经求出，然后n^2地更新每个正方形的L,R为可见的L,R ：
1.如果S[i] > S[j] （j=1~i-1），并且 seg[i].L < seg[j].R ， 那么 seg[j].R = seg[i].L
2.如果S[i] < S[j] .. , 并且 seg[i].L < seg[j].R ， 那么 seg[i].L = seg[j].R
--------------------------------------------------------------------------------------------------
代码：
#include <iostream>#include <cstdio>#include <cstring>#include <cstdlib>#include <cmath>#include <algorithm>using namespace std;//data segmentint S[55],b[55];struct Seg{ int L,R,LEN;}seg[55];//data endsint main(){ int n,i,j; double gen2 = sqrt(2.0); while(scanf("%d",&n)!=EOF && n) { for(i=1;i<=n;i++) scanf("%d",&S[i]); b[1] = S[1]; for(i=2;i<=n;i++) { b[i] = b[i-1]; for(j=i-1;j>=1;j--) b[i] = max(b[i],b[j] + 2*min(S[i],S[j])); } for(i=1;i<=n;i++) { seg[i].L = b[i] - S[i]; seg[i].R = b[i] + S[i]; seg[i].LEN = S[i]; } for(i=1;i<=n;i++) { for(j=1;j<i;j++) { if(seg[i].LEN > seg[j].LEN && seg[i].L < seg[j].R) seg[j].R = seg[i].L; if(seg[i].LEN < seg[j].LEN && seg[i].L < seg[j].R) seg[i].L = seg[j].R; } } int fir = 1; for(i=1;i<=n;i++) { if(seg[i].L < seg[i].R) { if(fir) cout<<i, fir = 0; else cout<<" "<<i; } } puts(""); } return 0;}
POJ 3347 Kadj Squares --扩展长度，几何，线段覆盖
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。