# 某岛

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

## ZJU 1391. Horizontally Visible Segments

### Analyse :

1. 根据几何可视关系，构图。
2. 统计可见三角的组数。

#### 1.纵向

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

#### 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;
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();
}

if (a > b) swap(a, b);
if (hash.find(a*N+b)!=hash.end()) return;
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())
}
}

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];
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 < 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;
}
}
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) 的一个推论，参见这里 ...