POJ 1177 Picture (선분 수 + 이산 화 + 스캐닝 라인) 상세 설명

다음으로 이동:http://www.cnblogs.com/shuaiwhu/archive/2012/04/22/2464876.html
POJ 1177 (선분 트 리 + 이산 화 + 스캐닝 라인), 제목 링크 는http://poj.org/problem?id=1177
본 문 제 를 풀 기 전에 선분 수 와 이산 화 가 무엇 인지 먼저 알 아야 합 니 다. 앞의 박문 선분 수 (segment tree) 를 보 세 요. 그 중에서 선분 수 와 이산 화 에 대한 설명 이 상대 적 으로 명확 합 니 다.
 
이 문제 에 대해 우리 의 사고방식 은 다음 과 같다.
1. 입력 한 N 개의 사각형 에 대해 2 * N 개의 세로 변 이 있 는데 우 리 는 이 변 을 스캐닝 라인 이 라 고 부른다.
2. 스 캔 라인 을 유지 하기 위해 struct ScanLine 을 만 듭 니 다.

struct ScanLine
{
  int x;//   
  int y1;//       
  int y2;//       
  int flag;//               ， AB，     ，  1，           ， CD，     ，  0
};

3. 배열 struct ScanLine scan [LEN] 을 만 듭 니 다.입력 값 을 저장 하고 y [LEN] 으로 모든 세로 좌 표를 저장 합 니 다.
4. scan 배열 을 정렬 합 니 다. 즉, 모든 세로 변 을 왼쪽 에서 오른쪽으로 정렬 합 니 다.y 를 정렬 하고 중복 값 을 제거 한 다음 에 분 산 된 다음 에 선분 트 리 를 만 듭 니 다.(PS: 선분 트 리 의 node [i]. left 와 node [i]. right 는 모두 분 산 된 값 으로 저장 되 어 있 습 니 다. y [node [i]. left] 와 y [node [i]. right] 는 실제 값 으로 저장 되 어 있 습 니 다. 코드 에서 쉽게 이해 할 수 있 습 니 다)
선분 트 리 노드 struct 노드

struct Node
{
  int left;
  int right;
  int count;//     
  int line;//        ，   [1,2]，[2,3]，[4,5]     ， line=2，   [1,2]，[2,3]    。            ，  ， AB EG     AK BL，     ，line=1，|AB|+|EG|=2*line*|AB|
  int lbd;//        ，     line   
  int rbd;//        ，     line   
  int m;//  ，        ， [2,8]  6
};

좋 습 니 다. 위 에 큰 프레임 을 만 들 고 스 캔 을 시 작 했 습 니 다.
1. 정렬 된 scan 배열 을 순서대로 입력 하고 삽입 라인 insert 함수 (입 변) 또는 reove 함수 (출 변) 를 실행 하 며 m 와 line 을 업데이트 합 니 다.
2. 한 번 스 캔 하지 않 고 둘레 perimeter 를 계산 해 야 합 니 다. 여기 서 우 리 는 그림 속 의 예 로 과정 을 설명 합 니 다.
   우선 AB 입 니 다. 선분 트 리 에 삽 입 됩 니 다. perimeter = perimeter + | AB |;
   그 다음 에 EG 입 니 다. 이 는 선분 트 리 에 삽 입 됩 니 다. 이 때 선분 트 리 의 루트 노드 의 측정 도 는 | EG | 의 값 입 니 다. 그러나 이전에 | AB | 를 추 가 했 기 때문에 | AB | 를 빼 야 합 니 다. 사실은 | KL | 을 뺀 다음 에 line * 2 * | AK | 를 추가 합 니 다. 여기 서 line 의 값 은 EG 를 삽입 하지 않 았 을 때 선분 트 리 의 뿌리 노드 의 line 값 입 니 다.
 
구체 적 인 코드 는 다음 과 같다.

#include <stdio.h>
#include <algorithm>
#define LEN 10000
using namespace std;

struct Node
{
  int left;
  int right;
  int count;//     
  int line;//        
  int lbd;//        
  int rbd;//        
  int m;//  
};

struct ScanLine
{
  int x;
  int y1;
  int y2;
  int flag;
};

struct Node node[LEN*4];
struct ScanLine scan[LEN];
int y[LEN];

void build(int l, int r, int i)
{
  node[i].left = l;
  node[i].right = r;
  node[i].count = 0;
  node[i].m = 0;
  node[i].line = 0;
  if (r - l > 1)
  {
    int middle = (l + r)/2;
    build(l, middle, 2*i + 1);
    build(middle, r, 2*i + 2);
  }
}

//    m
void update_m(int i)
{
  if (node[i].count > 0)
    node[i].m = y[node[i].right] - y[node[i].left];
  else if (node[i].right - node[i].left == 1)
    node[i].m = 0;
  else
  {
    node[i].m = node[2*i + 1].m + node[2*i + 2].m;
  }
}

//  line
void update_line(int i)
{
  if (node[i].count > 0)
  {
    node[i].lbd = 1;
    node[i].rbd = 1;
    node[i].line = 1;
  }
  else if (node[i].right - node[i].left == 1)
  {
    node[i].lbd = 0;
    node[i].rbd = 0;
    node[i].line = 0;
  }
  else
  {
    node[i].lbd = node[2*i + 1].lbd;
    node[i].rbd = node[2*i + 2].rbd;
    node[i].line = node[2*i + 1].line + node[2*i + 2].line - node[2*i + 1].rbd*node[2*i + 2].lbd;
  }
}

void insert(int l, int r, int i)
{
  //                 
  if (y[node[i].left] >= l && y[node[i].right] <= r)
    (node[i].count)++;
  else if (node[i].right - node[i].left == 1)
    return;
  else
  {
    int middle = (node[i].left + node[i].right)/2;
    if (r <= y[middle])
      insert(l, r, 2*i + 1);
    else if (l >= y[middle])
      insert(l, r, 2*i + 2);
    else
    {
      insert(l, y[middle], 2*i + 1);
      insert(y[middle], r, 2*i + 2);
    }
  }
  update_m(i);
  update_line(i);
}

void remove(int l, int r, int i)
{
  ////                 
  if (y[node[i].left] >= l && y[node[i].right] <= r)
    (node[i].count)--;
  else if (node[i].right - node[i].left == 1)
    return;
  else
  {
    int middle = (node[i].left + node[i].right)/2;
    if (r <= y[middle])
      remove(l, r, 2*i + 1);
    else if (l >= y[middle])
      remove(l, r, 2*i + 2);
    else
    {
      remove(l, y[middle], 2*i + 1);
      remove(y[middle], r, 2*i + 2);
    }
  }
  update_m(i);
  update_line(i);
}


bool cmp(struct ScanLine line1, struct ScanLine line2)
{
  if (line1.x == line2.x)
    return line1.flag > line2.flag;
  return (line1.x < line2.x);
}

int main()
{
  int n;
  scanf("%d", &n);
  int x1, y1, x2, y2;
  int i = 0;
  while (n--)
  {
    scanf("%d %d %d %d", &x1, &y1, &x2, &y2);
    scan[i].x = x1;
    scan[i].y1 = y1;
    scan[i].y2 = y2;
    scan[i].flag = 1;
    y[i++] = y1;
    scan[i].x = x2;
    scan[i].y1 = y1;
    scan[i].y2 = y2;
    scan[i].flag = 0;
    y[i++] = y2;
  }
  sort(y, y + i);
  sort(scan, scan + i, cmp);
  //y         
  int unique_count = unique(y, y + i) - y;
  //   ，     
  build(0, unique_count - 1, 0);
  
  int perimeter = 0;
  int now_m = 0;
  int now_line = 0;
  
  for (int j = 0; j < i; j++)
  {
    if (scan[j].flag)
      insert(scan[j].y1, scan[j].y2, 0);
    else
      remove(scan[j].y1, scan[j].y2, 0);
    if (j >= 1)
      perimeter += 2*now_line*(scan[j].x - scan[j-1].x);
    perimeter += abs(node[0].m - now_m);
    now_m = node[0].m;
    now_line = node[0].line;
  }

  printf("%d
", perimeter);
  return 0;
}

---