嘟嘟嘟
题意：给出一堆正方形的边长，且这些正方形都是(45 ^ {circ})斜放着并且紧挨着的，求从上往下看能看到几个正方形。
真是一道好题……跟计算几何关系不大。
想一下，如果我们能求出正方形的所有端点，那么这道题就变成了从上往下看，能看到几条线段了。
对于一个正方形(s_i)的左端点(s_i.l)，我们可以从(s_j(j < i))得到：即假设(s_i)和(s_j)紧挨着，那么如果(s_i.len leqslant s_j.len)，那么(s_i.l = s_j.l + s_j.len + s_i.len)，否则(s_i.l = s_j.l + s_j.len * 3 - s_i.len)。然后(s_i.l)就是这些所有运算结果的(max)值。最后更新(s_i.r = s_i.l + s_i.len * 2)。
讲道理这里面加上的应该是(s_i.len / sqrt{2})。然而怕掉精度，就都约掉了。
这样就把正方形转化成了线段。然后就是线段覆盖的问题了。一个比较清奇的思路是用别的线段的左右端点坐标修改自己的，如果最后自己的(s_i.l geqslant s_i.r)，说明这个线段已经全被挡死了。
#include<cstdio>
#include<iostream>
#include<cmath>
#include<algorithm>
#include<cstring>
#include<cstdlib>
#include<cctype>
#include<vector>
#include<stack>
#include<queue>
using namespace std;
#define enter puts("")
#define space putchar(' ')
#define Mem(a, x) memset(a, x, sizeof(a))
#define rg register
typedef long long ll;
typedef double db;
const int INF = 0x3f3f3f3f;
const db eps = 1e-8;
const int maxn = 55;
inline ll read()
{
ll ans = 0;
char ch = getchar(), last = ' ';
while(!isdigit(ch)) last = ch, ch = getchar();
while(isdigit(ch)) ans = (ans << 1) + (ans << 3) + ch - '0', ch = getchar();
if(last == '-') ans = -ans;
return ans;
}
inline void write(ll x)
{
if(x < 0) x = -x, putchar('-');
if(x >= 10) write(x / 10);
putchar(x % 10 + '0');
}
int n;
struct Square
{
int l, r, len;
}s[maxn];
int main()
{
while(scanf("%d", &n) && n)
{
for(int i = 1; i <= n; ++i)
{
s[i].len = read();
s[i].l = 0;
for(int j = 1; j < i; ++j)
{
int tp;
if(s[i].len <= s[j].len) tp = s[j].l + s[j].len + s[i].len;
else tp = s[j].l + s[j].len * 3 - s[i].len;
if(tp > s[i].l) s[i].l = tp;
}
s[i].r = s[i].l + (s[i].len << 1);
}
for(int i = 2; i <= n; ++i)
for(int j = 1; j < i; ++j)
if(s[j].len < s[i].len && s[j].r > s[i].l) s[j].r = s[i].l;
else if(s[j].len > s[i].len && s[j].r > s[i].l) s[i].l = s[j].r;
for(int i = 1; i <= n; ++i)
if(s[i].l < s[i].r) write(i), space;
enter;
}
return 0;
}
然而我还是把他归到了计算几何这个分类……