Kadj Squares - POJ 3347

时间:2024-11-01 16:37:38
题目大意:给一些序列的正方形的边长,然后让这个正方形倾斜45度,放在第一象限,一个角要紧挨着x轴,按照输入的顺序放下去,然后问最后从上往下看可以看到那些正方形?
分析:不能算是计算几何题......先求出来这个正方形的左右两端的位置,然后判断是否有比它高的正方形把它掩盖住就行了,为了避免浮点运算,可以用2*len当做对角线,也就是把所有边的长度扩大了sqrt(2)倍
代码如下:
========================================================================================================================================
#include<stdio.h>
#include<math.h>
#include<string.h>
#include<algorithm>
using namespace std; const int MAXN = ;
const double EPS = 1e-; struct Line{int L, R, len;}a[MAXN]; int main()
{
int N; while(scanf("%d", &N) != EOF && N)
{
memset(a, , sizeof(a)); for(int i=; i<N; i++)
{
scanf("%d", &a[i].len);
for(int j=; j<i; j++)
a[i].L = max(a[i].L, a[j].R-abs(a[j].len-a[i].len));
a[i].R = a[i].L + a[i].len * ;
} for(int i=; i<N; i++)
{
for(int j=; j<i; j++)
{
if(a[i].L < a[j].R && a[i].len < a[j].len)
a[i].L = a[j].R;
}
for(int j=i+; j<N; j++)
{
if(a[i].R > a[j].L && a[i].len < a[j].len)
a[i].R = a[j].L;
}
} for(int k=, i=; i<N; i++)
{
if(a[i].L < a[i].R)
{
if(k++)printf(" ");
printf("%d", i+);
}
}
printf("\n");
} return ;
}