本文主要是介绍NYOJ squares(计算几何+区间覆盖)，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
描述
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, and S4 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.
输入
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 n integers 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.
输出
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.
样例输入
4
3 5 1 4
3
2 1 2
0
样例输出
1 2 4
1 3
其实清楚一看就会发现其实每个正方形都对应一条线段，这个线段就是横向的对角线。所以问题就转化成求线段的覆盖问题，看哪些线段被盖住了。求线段覆盖的时候应为题目数据的要求范围很低，直接暴力随便什么的应该都没有问题，但是要注意一点，线段覆盖之前要先排序一下，因为哪根线段先放结果是不一样的。但我们又可以发现边长小的对角线一定在下面，所以考虑的时候应先按照边长的大小排序一下。接着我们再看一条线段是怎么确定的？其实就是左右端点，根据题目给的整数长度的边长，你会发现求出来的是浮点数的一条线段，浮点数是会产生误差的，之后判断的时候会误差，所以这其实需要一个巧妙的转化，就是说我们把正方行边长扩大sqrt(2),这就成为了数学中的相似，对结果是不影响的，仅相当于整个图都扩大了。
设当前的正方形为b, 紧挨着的前一个为f,扩大sqrt(2)倍的左右端点分别为b.l,f.l以及f.r, b.r, b.len, f.len是原输入数据的正方形的边长大小， 则有等式b.l=f.r-abs(b.len-f.len), b.r=b.l+2*b.len，这是简单几何，细心看一下就会发现，到此，这题应该就差不多了
AC代码：
# include <cstdio>
# include <cmath>
# include <cstdlib>
# include <cstring>
# include <algorithm>
using namespace std;
struct node{int r, l, len ,no;//左右端点，长度及其编号//r, l是扩大sqrt(2)后的左右端点距离,len是原数据长度
};
node s[60];
int ans[60];
int compare(node a, node b){return a.len<b.len;//边长最小最下面 ，排序一下
}
int main(){int n, i, j, k, Max_r, Min_l, cnt;while(scanf("%d", &n)!=EOF){if(n==0){break;}for(i=1; i<=n; i++){scanf("%d", &s[i].len);//输入数据 s[i].no=i;}cnt=0;//初始化s[1].l=0;s[1].r=2*s[1].len;Max_r=s[1].r;for(i=2; i<=n; i++){s[i].l=0;for(j=1; j<i; j++){s[i].l=max(s[i].l, s[j].r-abs(s[i].len-s[j].len));//枚举可能在第i个图形前面的正方形，更新Max_r }s[i].r=s[i].l+2*s[i].len;Max_r=max(Max_r, s[i].r);}sort(s+1, s+1+n, compare);//按边长排序一下 for(i=1; i<=n; i++){for(j=1; j<i; j++){if(s[j].l>=s[j].r){continue;}if(s[i].l<=s[j].l&&s[i].r>=s[j].r){s[j].r=s[j].l;}else if(s[i].l<=s[j].l&&s[i].r<=s[j].r&&s[i].r>=s[j].l){s[j].l=s[i].r;}else if(s[i].l>=s[j].l&&s[i].r>=s[j].r&&s[i].l<=s[j].r){s[j].r=s[i].l;}}}for(i=1; i<=n; i++){//满足要求的，记录编号 if(s[i].r>s[i].l){ans[cnt++]=s[i].no;}}sort(ans, ans+cnt);//按编号排序一下，最后再输出 for(i=0; i<=cnt-1; i++){if(i!=cnt-1){printf("%d ", ans[i]);}else{printf("%d\n", ans[i]);}}}return 0;
}
这篇关于NYOJ squares(计算几何+区间覆盖)的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
