PKU 1177 Picture .

 

 Picture

Time Limit: 2000MS		Memory Limit: 10000K
Total Submissions: 7116		Accepted: 3711

Description

A number of rectangular posters, photographs and other pictures of the same shape are pasted on a wall. Their sides are all vertical or horizontal. Each rectangle can be partially or totally covered by the others. The length of the boundary of the union of all rectangles is called the perimeter.

Write a program to calculate the perimeter. An example with 7 rectangles is shown in Figure 1.

The corresponding boundary is the whole set of line segments drawn in Figure 2.

The vertices of all rectangles have integer coordinates.

Input

Your program is to read from standard input. The first line contains the number of rectangles pasted on the wall. In each of the subsequent lines, one can find the integer coordinates of the lower left vertex and the upper right vertex of each rectangle. The values of those coordinates are given as ordered pairs consisting of an x-coordinate followed by a y-coordinate.

0 <= number of rectangles < 5000
All coordinates are in the range [-10000,10000] and any existing rectangle has a positive area.

Output

Your program is to write to standard output. The output must contain a single line with a non-negative integer which corresponds to the perimeter for the input rectangles.

Sample Input

7
-15 0 5 10
-5 8 20 25
15 -4 24 14
0 -6 16 4
2 15 10 22
30 10 36 20
34 0 40 16

Sample Output

228

Source

IOI 1998

呢个系我第一次做线段树离散化求矩形周长并，参考左Var Bob:^Joy关于线段树既文章。

8927215

GZHU1006100106

1177

Accepted

1528K

110MS

C++

3841B

2011-07-19 11:12:09

第一次编110ms效率唔系太高{= =}

 

下面附上代码：

#include <iostream>
#include <cmath>
#include <algorithm>
using namespace std;
#define MAXI 5005
#define INFI 10005

struct rect { int l, b, r, t; } rec[MAXI];
struct irec { int x, b, t, f; } xi[2 * MAXI];
int n, yi[2 * MAXI];

class segtree
{
    protected :
  struct node
  {
   node *ls, *rs;
   int l, r, c, m, cc;
   bool lb, rb;
  } *root, *p;
 public :
  void make(node *&x)
  {
   x = new node;
   x->ls = NULL;
   x->rs = NULL;
   x->l = x->r = x->c = x->m = x->cc = 0;
   x->lb = x->rb = 0;
  }
  segtree() { root = NULL; }
  int getm() { return root->m; }
  int getcc() { return root->cc; }
  void ins(int a, int b) { sins(root, a, b); }
  void del(int a, int b) { sdel(root, a, b); }
  void inti(int l, int r) { sint(root, l, r); }
  void lata(node *&x, int a, int b)
  {
   if (x->c > 0)
   {
    x->m = yi[x->r] - yi[x->l];
    x->lb = x->rb = x->cc = 1;
   }
   else if (x->c == 0 && x->l + 1 == x->r)
    x->lb = x->rb = x->m = x->cc = 0;
   else
   {
    x->lb = x->ls->lb;
    x->rb = x->rs->rb;
    x->m = x->ls->m + x->rs->m;
    x->cc = x->ls->cc + x->rs->cc;
    if (x->ls->rb == 1 && x->rs->lb == 1) x->cc--;
   }
  }
  void sint(node *&x, int l, int r)
  {
   make(x);
   x->l = l;
   x->r = r;
   if (l + 1 == r) return ;
   sint(x->ls, l, (l + r) / 2);
   sint(x->rs, (l + r) / 2, r);
  }
  void sins(node *&x, int a, int b)
  {
   int m = (x->l + x->r) / 2;
   if (a <= x->l && x->r <= b)
    x->c++;
   else
   {
    if (a < m) sins(x->ls, a, b);
    if (m < b) sins(x->rs, a, b);
   }
   lata(x, a, b);
  }
  void sdel(node *&x, int a, int b)
  {
   int m = (x->l + x->r) / 2;
   if (a <= x->l && x->r <= b)
    x->c--;
   else
   {
    if (a < m) sdel(x->ls, a, b);
    if (m < b) sdel(x->rs, a, b);
   }
   lata(x, a, b);
  }
};

bool operator < (irec &a, irec &b)
{
 if (a.x == b.x) return a.f < b.f;
 else return a.x < b.x;
}

int bs(int key, int l, int r)
{
 int m = (l + r) / 2; 
 if (yi[l] == key) return l;
 if (yi[r] == key) return r;
 if (yi[m] < key) return bs(key, m + 1, r);
 if (yi[m] > key) return bs(key, l, m - 1);
 return m;
}

int stat()
{
 segtree zkl;
 int i, sum = 0, cc = 0, tm = 0;
 zkl.inti(0, 2 * n - 1);
 for (i = 0; i < 2 * n; i++)
 {
  if (xi[i].f) zkl.del(xi[i].b, xi[i].t);
  else zkl.ins(xi[i].b, xi[i].t);

#if 0
  printf("dm = %d, lx = %d m = %d cc = %d dx = %d\n",
      zkl.getm() - tm,
      2 * (xi[i].x - xi[i - 1].x) * cc,
      zkl.getm(),
      cc,
      xi[i].x - xi[i - 1].x);
#endif

  sum += 2 * (xi[i].x - xi[i - 1].x) * cc;
  sum += abs(zkl.getm() - tm);
  tm = zkl.getm();
  cc = zkl.getcc();
 }
 return sum;
}

int main()
{
 int i, j;

 while (scanf("%d", &n) != EOF)
 {
  //Discrete Begin
  for (j = i = 0; i < n; i++)
  {
   scanf("%d%d%d%d",
      &rec[i].l,
      &rec[i].b,
      &rec[i].r,
      &rec[i].t);
   yi[j++] = rec[i].b;
   yi[j++] = rec[i].t;
  }
  sort(yi, yi + n * 2);
  //Discrete End
  //Event Sort Begin
  for (j = i = 0; i < n; i++)
  {
   xi[j].x = rec[i].l;
   xi[j].b = bs(rec[i].b, 0, 2 * n - 1);
   xi[j].t = bs(rec[i].t, 0, 2 * n - 1);
   xi[j++].f = 0;
   xi[j].x = rec[i].r;
   xi[j].b = xi[j - 1].b;
   xi[j].t = xi[j - 1].t;
   xi[j++].f = 1;
  }
  sort(xi, xi + n * 2);
  //Event Sort End

#if 0
  for (i = 0; i < n * 2; i++)
   printf("%d ", yi[i]);
  putchar('\n');
  for (i = 0; i < n * 2; i++)
   printf("%d ", xi[i].x);
  putchar('\n');
  for (i = 0; i < n * 2; i++)
   printf("x = %d, b = %d, t = %d, f = %d\n",
          xi[i].x, xi[i].b, xi[i].t, xi[i].f);
#endif
  printf("%d\n", stat());
 }

 return 0;
}

 

代码比较长= =，带有宏开关既系测试输出代码。

其实思想都唔系好复杂，我主要系想讲下离散化：

离散化既出现其实就系为左节省空间，好似上面果题甘样，线段树本来就唔系咩微型数据结构，如果吾离散化，实在会爆到恒{= =}。

做法有滴类似组合数学里面既一一对应，姐系等价转换，不过要保留原型，因为统计要用。

 

例如：

题目坐标范围【-10w， 10w】直接既捻法就系开一个20w大既线段树，但系加上卫星数据好明显会爆炸{= =}

我地再留意一下题目里面矩形数目既范围为5000，亦即有效坐标系最多1w个坐标，何必开20w呢？

所以我地可以做如下工作节省空间：

 

//Discrete Begin
  for (j = i = 0; i < n; i++)
  {
   scanf("%d%d%d%d",
      &rec[i].l,
      &rec[i].b,
      &rec[i].r,
      &rec[i].t);
   yi[j++] = rec[i].b;
   yi[j++] = rec[i].t;
  }
  sort(yi, yi + n * 2);
  //Discrete End

应该好容易睇出步骤就系先用数组yi储存所有矩形既y轴坐标，然后用sort排序, 得到如下序列:

 

实际数据：-6 -4 0 0 4 8 10 10 14 15 16 20 22 25

数据位置：0    1 2 3 4 5  6   7    8    9  10 11 12 13

 

跟住又注意到位置大小其实对应实际大小，所以我地储存既时候完全可以用位置“等效替代”实际数据{= =+}。

 

下面讲讲如何替代：

其实就系憨鸠鸠甘样开过另外一个数组直接二分查找代替原有y轴坐标{=_. =}

//Event Sort Begin
  for (j = i = 0; i < n; i++)
  {
   xi[j].x = rec[i].l;
   xi[j].b = bs(rec[i].b, 0, 2 * n - 1);
   xi[j].t = bs(rec[i].t, 0, 2 * n - 1);
   xi[j++].f = 0;
   xi[j].x = rec[i].r;
   xi[j].b = xi[j - 1].b;
   xi[j].t = xi[j - 1].t;
   xi[j++].f = 1;
  }
  sort(xi, xi + n * 2);
  //Event Sort End

 

关于线段树解决矩形问题baidu一下大把，有了解既应该知道呢类算法既一种感性理解就系想象有一条竖直扫描线，将矩形班油仔从左向右扫描一次

取得一滴统计数据。扫描数组xi其实模拟呢个。

注意到记录x坐标上y线段t(top)同埋b(bottom)既时候就用左bs(BinarySearch)用位置等效替代。

之后我地就可以直接使用呢滴相对位置鸟。

 

所以离散化其实系一样好简单既野，就系个名吓人一滴。

仲有我觉得叫离散化好似有滴怪，因为距实际操作系压缩坐标 {= =}