某岛

… : "…アッカリ~ン . .. . " .. .
March 3, 2011

ZJU 1391. Horizontally Visible Segments

Brief description :

给定一组垂直线段,求其中平行可见三角的组数。所谓的可见三角,指三组线段之间相互可见。

Analyse :

此题较难缠,通常可分为以下两个主要步骤。
1. 根据几何可视关系,构图。
2. 统计可见三角的组数。

下面主要讨论步骤一。颇为意外,这题根据扫描线或垂直或水平方向的不同,算法的表现会出现这么大的差别 …

1.纵向

对于每一只线段,建立一个插入事件和一个删除事件,排序之后从下向上扫描… 此处需要可以支持插入(Insert),删除(Delete)…以及返回前驱(Predecessor)、后继(Successor)的数据结构。


Illustration 1

Illustration 1. 纵向扫描,注意对插入事件和删除事件区别对待。


2.横向

如果想到先将端点×2,再拆“线段树”为“点树”的话,进而化归成“区间插入,区间询问的线段染色问题”,思维复杂度和代码量马上就会明显减少,这里实际上就将一只线段分成了三个判定点,线段右端的点和右边邻居的左端点相互重叠,请看下图。


Illustration 2

Illustration 2. 将一条线段分割成三块,这张图应该可说明这么做的奥妙。


#include 
#include 
#include 
#include 
#include 
#include 
using namespace std;
const int N = 8000;

struct Tnode{
	int l, r, c;
	int left, right;
} _T[2*N+1]; //?

int root, total;

struct Seg{
    int key, pos, sign;
    int id;
    friend bool operator <(Seg a, Seg b){
        return a.key < b.key || a.key == b.key && a.sign > b.sign;
    }
} L[2*N+1];
struct Re{
    int key, id;
	Re(): key(0), id(0) {}
	Re(int a, int b) :key(a), id(b) {}
    friend bool operator <(Re a, Re b){
        return a.key < b.key;
    }
} A[N];


set hash;
vector adj[N];
bool removed[N];
int n ,ans;

void _build(int &now, int a, int b){
	now = total++;
	
	_T[now].l = a, _T[now].r = b, _T[now].c = -1;
	if (a m) return _successor(_T[now].right, x);
		else {
			int _Left = _successor(_T[now].left, x);
			if (_Left == -1) return _successor(_T[now].right, x);
			else return _Left;
		}
	}
}



bool isVisible(int a, int b){
    if (a > b) swap(a, b);
    return hash.find(a*N+b)!=hash.end();
}


void addEdge(int a, int b){
    if (a > b) swap(a, b);
    if (hash.find(a*N+b)!=hash.end()) return;
    adj[a].push_back(b), adj[b].push_back(a);
    A[a].key++, A[b].key++;
    hash.insert(a*N+b);
}


void init1(){
	memset(L, 0, sizeof(L));
    cin >> n;
	
    int l, r, p;
    for (int i=0;i> n;
	
    int l, r, p;
    for (int i=0;i T; // The Binary-Search-Tree recorded the Seg position ...
	set::iterator XL, X, XR;
	
    while (i<2*n){
        cur = L[i].key;
        ii = i;
        while (L[ii].sign==1 && L[ii].key==cur){
            T.insert(Re(L[ii].pos, L[ii].id));
			ii++;
        }
		
		if (T.size()>=2){
			for (int j=i;jid, X->id);
				}
				
				XR = X, XR++;
				if (XR!=T.end())
					addEdge(X->id, XR->id);
			}
		}
		
		
        i = ii;
		
        while (L[ii].sign==-1 && L[ii].key==cur){
			T.erase(Re(L[ii].pos, -1));
            ii++;
        }
		
		if (T.size()>=2){
			for (int j=i;jid, XR->id);
				}
				T.erase(X);
			}
		}
        i = ii;
		
    }
}


void stat2(){
    memset(removed, false, sizeof(removed));
    
	stack S;
	for (int i=0;i temp;
		
		for (int j=0;j temp;
		
		for (int j=0;j temp;
		
		for (int j=0;j> d;
	while (d--){
		init1(); //init0(); //init1();
		stat0(); //stat1(); stat2();
	//	patch();
		cout << ans << endl;
	}
}
#include 
#include 
#include 
#include 
using namespace std;
const int N = 8000;

struct Tnode{
	int l, r, c;
    int left, right;
} T[4*N+1]; //..?
int root, total, _a, _b, _c, _x;

struct Seg{
	int l, r, key;
	friend bool operator <(Seg a, Seg b){
		return a.key < b.key;
	}
} S[N];

int hash[N];
vector adj[N];
int n ,ans;

void addEdge(int x, int y){
	adj[x].push_back(y);
}


void build(int& now, int a, int b){
	now = total++;
	T[now].l = a, T[now].r = b, T[now].c = -1;
	if (a < b){
		int m = (a + b) / 2;
		build(T[now].left, a, m);
		build(T[now].right, m+1, b);
	}
}


void query(int now){
	if (T[now].c!=-1){
		if (hash[T[now].c]!=_c){
			hash[T[now].c] = _c;
			addEdge(T[now].c, _c);
		}
	}
	else {
		if (T[now].l < T[now].r){
			int m = (T[now].l  + T[now].r) / 2;
			if (_a <= m) query(T[now].left); 	
			if (m < _b) query(T[now].right);
		}
	}
}



void insert(int now){
	if (_a <= T[now].l && T[now].r <= _b)
		T[now].c = _c;
	else{
		if (T[now].c != -1){
			T[T[now].left].c = T[T[now].right].c = T[now].c;
			T[now].c = -1;
		}
		int m = (T[now].l + T[now].r) / 2;
		if (_a <= m) insert(T[now].left);
		if (m < _b) insert(T[now].right);
	}
}


void init(){
	scanf("%d", &n);
	for (int i=0;i> d;
	while (d--){
		init(); stat(); 
		//patch();
		cout << ans << endl;
	}
}

Further discussion :

1. 方法一的代码巨大了点,主要是想尝试不同的写法 ... 但是时间似乎变化都不大,平均 0.88 s 左右,方法二时间 0.40 s 要更快 ...
2. 另外方法二还有诸多好处,例如构图时产生的边是严格按照从坐至右的顺序的 ... 可以不需要额外的一张散列表判断两点之间是否有边存在 ...
3. 平面图 (Planer graph) 至少包括一个度数小于6的点?(疑似是库斯图斯基定理 (Kuratowski's Theorem) 的一个推论,参见这里 ...

Reference :

—— 线段树专辑 notonlysuccess
poj 1436 Horizontally Visible Segments_云卷云舒_百度空间