计算几何 poj 3347

时间:2023-01-09 22:19:53

题意:依次给出n个正方形的边长,要求在第一象限内依次放入正方形,满足:

①放入第i个正方形时,第i个正方形与前面的正方形都不重合

②放入正方形时,要求一个顶点在x轴上,且坐标值最小

 

其实看这个图就懂规则了

计算几何 poj 3347

求放完所有正方形后,从高处向下照射竖直平行光,有部分会被照亮的正方形序号。

 

题解:

该题事实上只用到投影长度,将数据放大根号2倍,显然结果不变,但就只涉及整数计算,避免了精度问题

设正方形边长为s[i]=读入数据*根号2,顶点坐标为t[i]

考虑两件事——如何放正方形和如何判断是否被照亮:

放置①放第i个正方形的时候,扫描前i-1个正方形,now=max{s[k]+2*min{s[k],s[i]}},t[i]=max{now,s[i]}

判断②对第i个正方形,扫描1~i-1个正方形,l=max{s[j]+s[i]-(t[i]-t[j])},扫描i+1~n个正方形,r=max(r,s[j]+s[i]-(t[j]-t[i])),如果l+r<2*s[i],这个正方形就有被照亮的地方

 

写这种水题的时候常会失智,莫名写上半天

 

 

#include<cmath>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;

#define rep(i,a,b) for(int i=a;i<=b;++i)

int n,k,now,r,l;
int s[100],t[100];
int main()
{
    while (~scanf("%d",&n))
    {
        if (n==0) break;
        rep(i,1,n)
            scanf("%d",s+i);
        t[1]=s[1];
        rep(i,2,n)
        {
            now=0;
            rep(j,1,i-1) now=max(now,t[j]+2*min(s[i],s[j]));
            now=max(now,s[i]);
            t[i]=now;
        }
        rep(i,1,n)
        {
            l=0;r=0;
            rep(j,1,i-1) if (s[j]>s[i])
                l=max(l,s[j]+s[i]-(t[i]-t[j]));
            rep(j,i+1,n) if (s[j]>s[i])
                r=max(r,s[j]+s[i]-(t[j]-t[i]));
            if (l+r<2*s[i]) printf("%d ",i);
        }
        printf("\n");
    }
}