ZOJ :: Problems :: Show Problem

1436 -- Horizontally Visible Segments

　　用線段樹(shù)記錄表面能被看見(jiàn)的線段的編號(hào)，然后覆蓋的時(shí)候同時(shí)把能看到的線段記錄下來(lái)。這里要用到拆點(diǎn)，在兩個(gè)整點(diǎn)之間插入一個(gè)點(diǎn)。

　　最后O(n^2)統(tǒng)計(jì)三角形的個(gè)數(shù)，因?yàn)槊織l線段可以看見(jiàn)的另外的線段的條數(shù)不多，所以可以直接枚舉兩條邊。

代碼如下：

1 #include <cstdio> 2 #include <iostream> 3 #include <algorithm> 4 #include <cstring> 5 #include <set> 6 7 using namespace std; 8 9 const int N = 16666; 10 #define lson l, m, rt << 1 11 #define rson m + 1, r, rt << 1 | 1 12 #define root 0, 16000, 1 13 int cov[N << 2]; 14 15 void up(int rt) { 16 if (~cov[rt << 1] && cov[rt << 1] == cov[rt << 1 | 1]) cov[rt] = cov[rt << 1]; 17 else cov[rt] = -1; 18 } 19 20 void down(int rt) { if (~cov[rt]) cov[rt << 1] = cov[rt << 1 | 1] = cov[rt];} 21 22 void build(int L, int R, int l, int r, int rt) { 23 if (l >= r) { 24 cov[rt] = L <= l && r <= R ? 1 : 0; 25 return ; 26 } 27 int m = l + r >> 1; 28 build(L, R, lson); 29 build(L, R, rson); 30 up(rt); 31 } 32 33 set<int> edge[N >> 1]; 34 35 void update(int k, int L, int R, int l, int r, int rt) { 36 if (L <= l && r <= R && ~cov[rt]) { 37 if (cov[rt]) edge[k].insert(cov[rt]); 38 cov[rt] = k; 39 return ; 40 } 41 int m = l + r >> 1; 42 down(rt); 43 if (L <= m) update(k, L, R, lson); 44 if (m < R) update(k, L, R, rson); 45 up(rt); 46 } 47 48 struct Node { 49 int l, r, p; 50 } seg[N >> 1]; 51 52 bool cmp(Node a, Node b) { return a.p < b.p;} 53 54 int main() { 55 // freopen("in", "r", stdin); 56 int T, n; 57 scanf("%d", &T); 58 while (T-- && ~scanf("%d", &n)) { 59 for (int i = 1; i <= n; i++) { 60 scanf("%d%d%d", &seg[i].l, &seg[i].r, &seg[i].p); 61 seg[i].l <<= 1, seg[i].r <<= 1; 62 } 63 sort(seg + 1, seg + n + 1, cmp); 64 edge[1].clear(); 65 build(seg[1].l, seg[1].r, root); 66 for (int i = 2; i <= n; i++) { 67 edge[i].clear(); 68 update(i, seg[i].l, seg[i].r, root); 69 } 70 set<int>::iterator si, sj; 71 int ans = 0; 72 for (int i = 1; i <= n; i++) { 73 // cout << i << " : "; 74 // for (si = edge[i].begin(); si != edge[i].end(); si++) cout << *si << ' '; 75 // cout << endl; 76 for (si = edge[i].begin(); si != edge[i].end(); si++) { 77 int t = *si; 78 for (sj = edge[i].begin(); sj != edge[i].end(); sj++) { 79 ans += edge[t].find(*sj) != edge[t].end(); 80 } 81 } 82 } 83 printf("%d\n", ans); 84 } 85 return 0; 86 } View Code

?

?

——written by Lyon

?

轉(zhuǎn)載于:https://www.cnblogs.com/LyonLys/p/poj_1436_zoj_1391_Lyon.html

總結(jié)

以上是生活随笔為你收集整理的poj 1436 zoj 1391 Horizontally Visible Segments (Segment Tree)的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

如果覺(jué)得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。