題干：

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?Siintersect 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?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.

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

解題報告：

? ? ?掃描線忘了啊，不然就試試掃描線了。

AC代碼：

#include<iostream> #include<algorithm> #include<cstdio> #include<queue> #include<map> #include<vector> #include<set> #include<string> #include<cmath> #include<cstring> #define ll long long #define pb push_back #define pm make_pair #define fi first #define se second using namespace std; const int MAX = 200 + 5; struct Node {ll l,r;ll s;//邊長 } node[MAX],nnnn[MAX]; ll Abs(ll x) {if(x < 0) x=-x;return x; } int main() {int n;while(~scanf("%d",&n) && n) {for(int i = 1; i<=n; i++) {scanf("%lld",&node[i].s);node[i].l = 0;//先初始化一波for(int j = 1; j<i; j++) {node[i].l = max(node[i].l,node[j].r - (ll)Abs(node[j].s-node[i].s));} node[i].r = node[i].l + 2*node[i].s;}for(int i = 1; i<=n; i++) { // nnnn[i] = node[i];//這個必須有、、、、 for(int j = 1; j<i; j++) {if(node[i].l < node[j].r && node[i].s < node[j].s) {node[i].l = node[j].r;//即左邊只能看到 這里 這么遠// }}for(int j = i+1; j<=n; j++) {if(node[i].r > node[j].l && node[i].s < node[j].s) {node[i].r = node[j].l;}}}int flag = 1;for(int i = 1; i<=n; i++) {if(node[i].l < node[i].r) {if(flag) {flag=0;printf("%d",i);}else printf(" %d",i); }}puts("");}return 0 ;}

想問為什么這樣就wa？？？？兩者就那一個地方有區別（node或者nnnn）

#include<iostream> #include<algorithm> #include<cstdio> #include<queue> #include<map> #include<vector> #include<set> #include<string> #include<cmath> #include<cstring> #define ll long long #define pb push_back #define pm make_pair #define fi first #define se second using namespace std; const int MAX = 200 + 5; struct Node {ll l,r;ll s;//邊長 } node[MAX],nnnn[MAX]; ll Abs(ll x) {if(x < 0) x=-x;return x; } int main() {int n;while(~scanf("%d",&n) && n) {for(int i = 1; i<=n; i++) {scanf("%lld",&node[i].s);node[i].l = 0;//先初始化一波for(int j = 1; j<i; j++) {node[i].l = max(node[i].l,node[j].r - (ll)Abs(node[j].s-node[i].s));} node[i].r = node[i].l + 2*node[i].s;}for(int i = 1; i<=n; i++) {nnnn[i] = node[i];//這個必須有、、、、 for(int j = 1; j<i; j++) {if(node[i].l < node[j].r && node[i].s < node[j].s) {nnnn[i].l = node[j].r;//即左邊只能看到 這里 這么遠// }}for(int j = i+1; j<=n; j++) {if(node[i].r > node[j].l && node[i].s < node[j].s) {nnnn[i].r = node[j].l;}}}int flag = 1;for(int i = 1; i<=n; i++) {if(nnnn[i].l < nnnn[i].r) {if(flag) {flag=0;printf("%d",i);}else printf(" %d",i); }}puts("");}return 0 ;}

?

創作挑戰賽新人創作獎勵來咯，堅持創作打卡瓜分現金大獎

總結

以上是生活随笔為你收集整理的【POJ - 3347 】Kadj Squares （计算几何，思维 或 扫描线）的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。