POJ3347 Kadj Squares

嘟嘟嘟

题意：给出一堆正方形的边长，且这些正方形都是\(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;

}

然而我还是把他归到了计算几何这个分类……

巴特西

POJ3347 Kadj Squares

最新文章

热门文章