Brief description :
给定一组垂直线段，求其中平行可见三角的组数。所谓的可见三角，指三组线段之间相互可见。
Analyse :
此题较难缠，通常可分为以下两个主要步骤。
1. 根据几何可视关系，构图。
2. 统计可见三角的组数。
下面主要讨论步骤一。颇为意外，这题根据扫描线或垂直或水平方向的不同，算法的表现会出现这么大的差别 …
1.纵向
对于每一隻线段，建立一个插入事件和一个删除事件，排序之后从下向上扫描… 此处需要可以支持插入（Insert），删除（Delete）…以及返回前驱（Predecessor）、后继（Successor）的数据结构。
Illustration 1. 纵向扫描，注意对插入事件和删除事件区别对待。
2.横向
如果想到先将端点×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_云卷云舒_百度空间
