Kadj Squares

http://acm.pku.edu.cn/JudgeOnline/problem?id=3347

Description

In this problem, you are given a sequence S₁, S₂, ..., S_n 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 b_i be the x coordinates of the bottom vertex of S_i. First, put S₁ such that its left vertex lies on x=0. Then, put S₁, (i > 1) at minimum b_i such that

• b_i > b_i-1 and
• the interior of S_i does not have intersection with the interior of S₁...S_i-1.

The goal is to find which squares are visible, either entirely or partially, when viewed from above. In the example above, the squares S₁, S₂, and S₄ have this property. More formally, S_i is visible from above if it contains a point p, such that no square other than S_i 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 n integers between 1 to 30, where the ith number is the length of the sides of S_i. 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.2

Source

Tehran 2006


Solving

수열 S1, S2, ..., Sn이 주어진다. Si는 i번째 정사각형의 한 변의 길이이다. 각 정사각형들을 45도 기울여 왼쪽으로 타이트하게 붙여 위에서 내려다 봤을 때 눈에 보이는 정사각형의 번호를 구하라.

우선 문제에서 처럼 왼쪽으로 사각형들을 밀착시켰을 때, 각 사각형의 중심의 x좌표값을 구해보자

사각형이 45도 기울어져 있기 때문에 사각형의 변이 바닥에 사영되었을 때 길이는 √2/2 가 된다. 하지만 이 값을 직접 사용하게되면 플로팅포인트 연산을 해야하는 부담감과 더욱이 어쩔 수 없이 생기는 오차때문에 정확한 답을 기대하기 힘들다. 하지만 구하고자 하는 포인트에 집중해 보면 이런 딜레마를 해결할 수 있다.

45도로 기울어진 사각형의 가로 길이는 사각형의 한변의 길이와 비례한다는 것에 주목하면 궂이 x좌표의 정확한 값을 구하기 위해 변의 길이에 √2/2를 곱할 필요없이 변의 길이를 그대로 사용해도 된다는 사실을 발견할 수 있다.

이제 처음에 구하고자 했던 사각형의 중심의 x좌표를 구하자.
i번째 사각형의 중심의 좌표를 Ci, 왼쪽끝의 좌표를 Li, 오른쪽 끝의 좌표를 Ri라고 하면 다음과 같다.

첫번재 사각형은 의심할 여지 없이 S0에 위치하게 된다. 따라서 C0 = S0

두번째 사각형을 따져보자
S0 = S1 인 경우 C1 = S0 + S1이 된다.
S0 < S1 인 경우 S1 - S0 만큼 두 사각형이 겹치게 된다. 따라서 C1 = C0 + 2*S0
S0 > S1 인 경우 S0 - S1 만큼 두 사각형이 겹치게 된다. 따라서 C1 = C0 + 2*S1

세번째 사각형부터는 그 앞에 있는 모든 사각형들과 비교하며 좌표를 계산하여 가장 큰값이 현재 사각형의 중심의 좌표가 된다. 즉 세번째 사각형의 경우 상황에 따라 첫번째 사각형과 마주칠수도 있고 두번째 사각형과 마주칠 수도 있다. 따라서 양쪽의 경우의 수를 다 구한뒤 더 큰 값을 취한다(가장 큰 값을 내는 사각형과 마주치고 있다)

양쪽끝의 좌표는 다음과 같이 구한다.
Li = Ci - Si
Ri = Ci + Si

이제 중심의 좌표를 기준으로 사각형 들을 소팅한 뒤에 위에서 내려다 봤을 때 보이는 사각형을 구한다. 이 루틴은 이중루프를 돌면서 구할 수 있다. 어떤 사각형 Sj가 현재 검사하는 사각형 Si보다 위에 있으려면 Sj > Si이어야 한다. 그러면서 Sj가 Si를 완전히 가리려면 Lj <= Li && Rj >= Ri를 만족해야 한다. 이 세 조건을 모두 만족하는 다른 사각형이 없으면 Si는 위에서 내려다 봤을때 보인다.

#include <cstdlib> #include <cstdio> #include <vector> #include <algorithm> #include <cmath> using namespace std; struct SQUARE { int number; int len; int l; int r; int c; }; int sqg(SQUARE a, SQUARE b) {return a.len < b.len;} int main() { int n; while (scanf("%d", &n) > 0) { if (n == 0) break; int i,j,k; vector<SQUARE> sq(n); for (i = 0; i < n; i++) { int len; scanf("%d", &len); sq[i].number = i+1; sq[i].len = len; int maxCenter = len; for (j = 0; j < i; j++) { int pos; if (sq[j].len <= sq[i].len) pos = sq[j].c + 2 * sq[j].len; else pos = sq[j].c + 2 * sq[i].len; if (maxCenter < pos) maxCenter = pos; } sq[i].c = maxCenter; sq[i].l = maxCenter - len; sq[i].r = maxCenter + len; } sort(sq.begin(), sq.end(), sqg); vector<int> res; for (i = 0; i < n; i++) { double l = sq[i].l; double r = sq[i].r; for (j = i+1; j < n; j++) { if (sq[i].len == sq[j].len) continue; if (l < sq[j].r && l >= sq[j].l) l = sq[j].r; if (r > sq[j].l && r <= sq[j].r) r = sq[j].l; } if (l < r) res.push_back(sq[i].number); } sort(res.begin(), res.end()); for (i = 0; i <res.size(); i++) { if (i) printf(" "); printf("%d", res[i]); } printf("\n"); } return 0; }