Description
In this problem, you are given a sequence S1, S2, ..., Sn of squares of different sizes. The sides of the squares are integer numbers. We locate the squares on the positive x-y quarter of the plane, such that their sides make 45 degrees with x and y axes, and one of their vertices are on y=0 line. Let bi be the x coordinates of the bottom vertex of Si. First, put S1 such that its left vertex lies on x=0. Then, put S1, (i > 1) at minimum bi such that
- bi > bi-1 and
- the interior of Si does not have intersection with the interior of S1...Si-1.
The goal is to find which squares are visible, either entirely or partially, when viewed from above. In the example above, the squares S1, S2, andS4 have this property. More formally, Si is visible from above if it contains a point p, such that no square other than Si intersect the vertical half-line drawn from p upwards.
Input
The input consists of multiple test cases. The first line of each test case is n (1 ≤ n ≤ 50), the number of squares. The second line contains nintegers between 1 to 30, where the ith number is the length of the sides of Si. The input is terminated by a line containing a zero number.
Output
For each test case, output a single line containing the index of the visible squares in the input sequence, in ascending order, separated by blank characters.
Sample Input
4
3 5 1 4
3
2 1 2
0
Sample Output
1 2 4
1 3
题意：变长不同的n个正方形，斜45度按顺序平放在坐标轴上，尽量靠左但不能跃出x=0，
问从上往下看，哪些正方形是可见的。
题解：1、假如前i-1个正方形位置都确定了，那么可以让第i个正方形与前i-1个正方形每个
都计算一次它如果和它相依靠的话左边坐标的值，然后取一个最大的便是这个正方形
的左端点位置。
2、对于j<i的正方形，如果i的边长大于j那么j的最右能看到的部分就不会比i的最左端
点大，反之，i的最左能看到的部分就不会比j最右端点小。
3、通过第2步筛选，将那些最左能看到的端点比最右能看到端点大或等于的去掉，剩
下的就是所要求的。
注意：为避免浮点数运算，根号2约掉了，代码中的边长实际上指的就是边长/根号2，也可以
将该题理解为将正方形投影到x轴上。
#include <iostream>
#include <string.h>
#include <math.h>
#include <algorithm>
using namespace std;
struct sa
{
int l,r,len;
}data[];
int main()
{
int n;
while(cin>>n&&n)
{
memset(data,,sizeof(data));
for(int i=;i<n;i++)
{
cin>>data[i].len;
//现在把图形扩大根号2倍
//边长现在是根号2*len 而len现在指的是对角线的一半的长度
for(int j=;j<i;j++)
//当l是最大值的时候,abs那段是两个图形的重叠部分
//每一个data[j].r求的都是假设ij有重合部分的情况的l
//但是只有真正重合的j能求出真正的l也就是最大的l
//根据等腰三角形性质画一画就明白怎么推的了
//等腰三角形指的是以x周为斜边的那个 两个45度
data[i].l=max(data[i].l,data[j].r-abs(data[i].len-data[j].len));
data[i].r=data[i].l+*data[i].len;
}
for(int i=;i<n;i++)
{
for(int j=;j<i;j++)
{
if(data[j].r>data[i].l)//可更新 有两种情况
{
if(data[j].len<data[i].len) //右面大
data[j].r=data[i].l;//右面的把左面的挡住了一块
else
data[i].l=data[j].r;//左面的把右面的挡住了一块
}
}
}
bool first=true;
for(int i=;i<n;i++)
{
if(data[i].l<data[i].r)
{
if(first)
{
cout<<i+;
first=false;
}
else
cout<<" "<<i+;
}
}
cout<<endl;
}
return ;
}