[poj] 3347 Kadj Square || 计算几何的“线段覆盖”

原题

多组数据，给出n个正方形的边长，使他们以45度角倾斜的情况下最靠左（在第一象限内），如图。求从上看能看到哪几个完整的正方形。

借鉴于https://www.cnblogs.com/Ritchie/p/5491758.html

#include<cstdio>

#include<algorithm>

#include<cstring>

using namespace std;

int n;

struct hhh

{

    int len,l,r;

}dt[55];

int main()

{

    while (~scanf("%d",&n) && n)

    {

	memset(dt,0,sizeof(dt));

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

	{

	    scanf("%d",&dt[i].len);

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

		dt[i].l=max(dt[i].l,dt[j].r-abs(dt[i].len-dt[j].len));

	    dt[i].r=dt[i].l+2*dt[i].len;

	}

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

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

		if (dt[j].r>dt[i].l)

		{

		    if (dt[j].len<dt[i].len)

			dt[j].r=dt[i].l;

		    else

			dt[i].l=dt[j].r;

		}

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

	    if (dt[i].l<dt[i].r)

		printf("%d ",i+1);

	putchar('\n');

    }

    return 0;

}

巴特西

[poj] 3347 Kadj Square || 计算几何的“线段覆盖”

原题

最新文章

热门文章