线段树-poj1177-N个矩形求边长（离散化+扫描线）

package com.ljn.base;

import java.util.Arrays;
import java.util.Comparator;
import java.util.Set;
import java.util.TreeSet;

/**
 * POJ 1177 (线段树+离散化+扫描线)，题目链接为http://poj.org/problem?id=1177
 * 
 * 关于扫描线（ScanLine）和线段树结点（Node）各字段的定义，请参看陈宏的论文：
 * 《数据结构的选择与算法效率——从IOI98试题PICTURE谈起》链接为http://wenku.baidu.com/view/1856cf84b9d528ea81c77918.html
 * 强烈建议将上面的论文看一遍，因为各字段的定义和计算不好理解
 * 
 * 个人理解：
 * 离散化：
 * 例如有如下三条线段：(-100,-90)(10,20)(3333,4444)
 * 如果建立的线段树是Tree(-100, 4444)那会浪费相当多的空间
 * 所谓离散化就是把这三条线段映射成：(0,1)(2,3)(4,5)建立的线段树为Tree(0,5)
 * 插入和删除时要注意把真实值映射成离散值再操作树
 * 本题在解题时还要注意把数组y的值去重
 * 
 * 轮廓周长计算方法：
 * 有两种
 * 1.先扫描竖边，再扫描横边，两者相加
 * 2.只扫描竖边，一边扫描一边加上横边。扫描时前后两条扫描边在x轴的距离则为横边的长度
 * 下面的代码是按第2种方法来执行的
 * 
 * 采用上面的第2种方法时，横边的计算上面讲了，那竖边怎么办呢？
 * 因为前后两条扫描线是有可能有重叠的，因此周长的增量只是这两条线在y轴上的长度差（|Tree1.M - Tree2.M|）
 * 
 * 1.下面的代码用数组来保存线段树
 * 用链表会更用更少的空间，有空再写一个
 * 2.下面的线段树的叶子结点为[i,i+1]，而不是[i,i]
 * 
 * @author lijinnan
 */
public class SegmentTreePOJ1177 {

    //扫描线（竖线）
    class ScanLine {
        int x;  //x坐标
        int y1; //顶点的y坐标
        int y2; //底端点的y坐标
        int flag;   //1=入边，0=出边。从左到右扫描时，矩形的左边称为入边，右边称为出边
    }

    //线段树的结点，也就是一条线段
    class Node {
        int left;   //线段的左值
        int right;  //线段的右值
        int count;  //线段出现的次数
        int line;   //线段跨越了几个段。如对于Node[1,5]，三个子结点[1,2]，[2,3]，[4,5]线段被覆盖，则line=2，因为 [1,2]，[2,3]是连续的
        int lbd;    //左值是否出现（覆盖）过
        int rbd;    //右值是否出现（覆盖）过
        int m;      //以本结点为根结点的子树代表的长度
    }
    
    Node[] node;
    ScanLine[] scan;
    int[] y;
    
    public static void main(String[] args) {
        //左下方和右上方的两个点(x1,y1)(x2,y2)定义了一个矩形。共7个矩形，14个点
        int[][] input = {
                { -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, },
        };
        new SegmentTreePOJ1177().process(input);
    }


    public void process(int[][] input) {
        init(input.length);
        
        //读入并保存扫描线
        int i = 0;
        for (int[] segment : input) {
            scan[i].x = segment[0];
            scan[i].y1 = segment[1];
            scan[i].y2 = segment[3];
            scan[i].flag = 1;
            y[i] = segment[1];
            i++;
            scan[i].x = segment[2];
            scan[i].y1 = segment[1];
            scan[i].y2 = segment[3];
            scan[i].flag = 0;
            y[i] = segment[3];
            i++;
        }
        
        //将扫描线按x坐标的大小从左到右排序；x坐标相等的，入边在前，出边在后
        Arrays.sort(scan, new Comparator<ScanLine>() {
            public int compare(ScanLine line1, ScanLine line2) {
                if (line1.x == line2.x) {
                    return line1.flag - line2.flag;
                }
                return line1.x - line2.x;
            }
        });
        
        //得到离散化后的值再建线段树
        Set<Integer> set = sortAndMakeUnique(y);
        int N = set.size();
        y = new int[N];
        int j = 0;
        for(Integer ele : set) {
            y[j++] = ele;
        }
        build(0, N - 1, 0);
        
        int perimeter = 0;
        int now_m = 0;
        int now_line = 0;
        for(int k = 0, len = scan.length; k < len; k++) {
            if (scan[k].flag == 1) {
                insert(scan[k].y1, scan[k].y2, 0);
            } else {
                remove(scan[k].y1, scan[k].y2, 0);
            }
            if (k >= 1) {
                perimeter += 2 * now_line * (scan[k].x - scan[k - 1].x);    //加上两条横边
            }
            perimeter += Math.abs(node[0].m - now_m);   //加上竖边
            now_m = node[0].m;
            now_line = node[0].line;
        }
        System.out.println("perimeter = " + perimeter); //expected:228
    }
    
    
    /**
     * 初始化
     * @param rectangleCount 矩形的个数
     * 竖边（扫描线）的条数为rectangleCount * 2
     * y轴坐标的坐标值也是rectangleCount * 2
     */
    public void init(int rectangleCount) {
        int N = rectangleCount * 2;
        int nodeCount = getNodeCount(N);
        node = new Node[nodeCount];
        for(int i = 0, len = node.length; i < len; i++) {
            node[i] = new Node();
        }
        scan = new ScanLine[N];
        for(int i = 0, len = scan.length; i < len; i++) {
            scan[i] = new ScanLine();
        }
        y = new int[N];
    }
    
    /**
     * 求得线段树的结点个数
     * 线段树用数组存储，若表示的范围是[1,n]那么这个完全二叉树的高度为h=ceil(log2N)
     * 结点数为：1 + 2 + 4 + 8 + ... + 2^h （根结点为第0层）
     */
    public int getNodeCount(int n) {
        int result = 1;
        int base = 1;
        int height = (int) Math.ceil(Math.log(n) / Math.log(2));
        for(int i = 1; i <= height; i++) {
            base *= 2;
            result += base;
        }
        return result;
    }
    
    //Set可去重，TreeSet可排序
    private Set<Integer> sortAndMakeUnique(int[] y) {
        Set<Integer> set = new TreeSet<Integer>();
        for (int i : y) {
            Integer j = Integer.valueOf(i);
            set.add(j);
        }
        return set;
    }
    
    public void build(int left, int right, int i) {
        node[i].left = left;
        node[i].right = right;
        node[i].lbd = 0;
        node[i].rbd = 0;
        node[i].count = 0;
        node[i].line = 0;
        node[i].m = 0;
        if (right - left > 1) {
            int mid = left + (right - left) / 2;
            build(left, mid, 2 * i + 1);
            build(mid, right, 2 * i + 2);
        }
    }

    public void insert(int left, int right, int i) {
        if (y[node[i].left] == left && y[node[i].right] == right) {
            node[i].count++;
        } else {
            if (node[i].right - node[i].left == 1) {
                return;
            } else{
                int mid = node[i].left + (node[i].right - node[i].left) / 2;
                if (right <= y[mid]) {
                    insert(left, right, 2 * i + 1);
                } else if (left >= y[mid]){
                    insert(left, right, 2 * i + 2);
                } else {
                    insert(left, y[mid], 2 * i + 1);
                    insert(y[mid], right, 2 * i + 2);
                }
            }
        }
        update_m(i);
        update_line(i);
    }
    
    public void remove(int left, int right, int i) {
        if (y[node[i].left] == left && y[node[i].right] == right) {
            node[i].count--;
        } else {
            if (node[i].right - node[i].left == 1) {
                return;
            } else{
                int mid = node[i].left + (node[i].right - node[i].left) / 2;
                if (right <= y[mid]) {
                    remove(left, right, 2 * i + 1);
                } else if (left >= y[mid]) {
                    remove(left, right, 2 * i + 2);
                } else {
                    remove(left, y[mid], 2 * i + 1);
                    remove(y[mid], right, 2 * i + 2);
                }
            }
        }
        update_m(i);
        update_line(i);
    }
    
    public 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;
            }
        }
    }
    
    public 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].lbd;
                node[i].line = node[2 * i + 1].line + node[2 * i + 2].line;
                if (node[2 * i + 1].rbd == 1 && node[2 * i + 2].lbd == 1) { //左右孩子结点刚好连续上了，则跨越的段数要减1
                    node[i].line--;
                }
            }
        }
    }
    
}