Description
There is a number of disjoint vertical line segments in the plane. We say that two segments are horizontally visible if they can be connected by a horizontal line segment that does not have any common points with other vertical segments. Three different vertical segments are said to form a triangle of segments if each two of them are horizontally visible. How many triangles can be found in a given set of vertical segments?Input
The first line of the input contains exactly one positive integer d equal to the number of data sets, 1 <= d <= 20. The data sets follow.Output
The output should consist of exactly d lines, one line for each data set. Line i should contain exactly one integer equal to the number of triangles in the i-th data set.Sample Input
1 5 0 4 4 0 3 1 3 4 2 0 2 2 0 2 3
Sample Output
1
題意：平面上有幾個垂直的線，現在有如果兩個垂直的線之間有一條連線並不會經過其他的垂直線的話，那麼我們就說這兩個線是互相可視的，現在求三條兩兩互相可視的解
思路:覆蓋問題，我們首先排序，然後往前找之前有沒有可視的解，這樣並不會影響到結果，因為這種可視是相互的，
然後因為我們線段樹的單位是線段，不是點，所以我們需要將每次的值*2，這樣能避免：兩個相鄰的點之間的空的距離被覆蓋到
#include#include #include #include #include #define lson(x) ((x) << 1) #define rson(x) ((x) << 1 | 1) using namespace std; const int maxn = 8005<<1; vector ve[maxn<<1]; int vis[maxn<<1]; struct seg { int w; }; struct segment_tree { seg node[maxn<<2]; void build() { memset(node, -1, sizeof(node)); } void push(int pos) { if (node[pos].w != -1) { node[lson(pos)].w = node[rson(pos)].w = node[pos].w; node[pos].w = -1; } } void modify(int l, int r, int pos, int x, int y, int z) { if (x <= l && y >= r) { node[pos].w = z; return; } push(pos); int m = l + r >> 1; if (x <= m) modify(l, m, lson(pos), x, y, z); if (y > m) modify(m+1, r, rson(pos), x, y, z); } void query(int l, int r, int pos, int x, int y, int z) { if (node[pos].w != -1) { if (!vis[node[pos].w]) { vis[node[pos].w] = 1; ve[z].push_back(node[pos].w); } return; } if (l == r) return; int m = l + r >> 1; if (x <= m) query(l, m, lson(pos), x, y, z); if (y > m) query(m+1, r, rson(pos), x, y, z); } } tree; struct segment { int a, b, x; bool operator <(const segment &tmp) const { return x < tmp.x; } } a[maxn]; int main() { int t, n; scanf("%d", &t); while (t--) { scanf("%d", &n); int l = 0x3f3f3f3f, r = -1; for (int i = 0; i < n; i++) { scanf("%d%d%d", &a[i].a, &a[i].b, &a[i].x); a[i].a *= 2; a[i].b *= 2; } sort(a, a+n); tree.build(); for (int i = 0; i < n; i++) ve[i].clear(); for (int i = 0; i < n; i++) { memset(vis, 0, sizeof(vis)); tree.query(0, maxn<<1, 1, a[i].a, a[i].b, i); tree.modify(0, maxn<<1, 1, a[i].a, a[i].b, i); } int ans = 0; for (int i = 0; i < n; i++) { int cnt = i; for (int j = 0; j < ve[cnt].size(); j++) { int cur = ve[cnt][j]; for (int k = 0; k < ve[cur].size(); k++) for (int l = 0; l < ve[cnt].size(); l++) if (ve[cur][k] == ve[cnt][l]) ans++; } } printf("%d\n", ans); } return 0; }
