poj3347

題意：給予n個正方形，要求45°角放置，最左邊的正方形緊貼Y軸，所有的正方形的下面的端點都在X軸上。然後按照正方形不能交錯但要盡可能的挨着的原則，擺放，最後輸出從上往下看能看到的正方形的編号。

方法：看了各種Discuss和解題報告，發現有個人的思路很不錯，但他是将坐标紙縮小√2，這樣并不能避免小數，其實擴大√2倍就能避免小數了。辦法是，每新增一個正方形，就讓他與左側的每一個正方形貼緊，求的其左端坐标，最終結果一定是最大的那個。然後求的相應的最右端坐标。這樣就轉化為了線段，最後用樸素的n2算法求出每條線段沒有被覆寫的長度，如果長度大于0，即可輸出

WA點：移位運算符>>優先級比+低，故a = b + c << 1等價于 a = （(b + c) << 1）;另外，乘以2是移一位，不是兩位！

代碼：

#include <iostream>

#include <cstring>

#include <algorithm>

#include <cstdio>

using namespace std;

struct Segment

{

int left,right,len;

};

Segment seg[50];

int main()

{

int n;

while(cin >> n,n)

{

for(int i = 0; i < n; i++)

{

cin >> seg[i].len;

seg[i].left = 0;

for(int j = 0; j < i; j++)

{

seg[i].left = max(seg[i].left,seg[j].right - abs(seg[i].len - seg[j].len));

}

seg[i].right = seg[i].left + seg[i].len * 2;

}

for(int i = 1; i < n; i++)

{

for(int j = 0; j < i; j++)

{

if(seg[i].left < seg[i].right)

{

if(seg[i].len > seg[j].len && seg[i].left < seg[j].right)

seg[j].right = seg[i].left;

else if(seg[i].len < seg[j].len && seg[i].left < seg[j].right)

seg[i].left = seg[j].right;

}

}

}

for(int i = 0; i < n; i++)

{

if(seg[i].left < seg[i].right)

cout << i + 1 << " ";

}

cout << endl;

}

return 0;

}