本文共 2298 字，大约阅读时间需要 7 分钟。
题中定义了什么叫做可见线段。所谓可见线段就是在给定的垂直与x轴的直线中，能够在两个直线之间连接一条平行线，并且这条平行线不与任何其他的直线相交。
WA一次，就是因为没有考虑到在建立点树的过程中会出现将 [1, 2] 和 [3, 4] 视为一条连接的直线，所以最后给坐标乘以一个2.
代码如下：
#include #include #include #include #include #include #define MAXN 8000 using namespace std; struct Seq { int y1, y2, x; bool operator < (Seq t) const { return x < t.x; } }e[MAXN+5]; struct { int l, r, who; }seg[MAXN*8]; map m[MAXN+5]; void build(int f, int l, int r) { int mid = l+r >> 1; seg[f].l = l, seg[f].r = r; seg[f].who = 0; if (r > l) { build(f<<1, l, mid); build(f<<1|1, mid+1, r); } } void up(int f) { if (seg[f<<1].who == seg[f<<1|1].who) seg[f].who = seg[f<<1].who; else seg[f].who = -1; } void modify(int f, int l, int r, int who, map *m) { int mid = seg[f].l+seg[f].r >> 1; if (seg[f].l == l && seg[f].r == r && (seg[f].who != -1 || r==l)) { if (seg[f].who != -1 && seg[f].who != 0) m[who][seg[f].who] = 1; seg[f].who = who; } else if (seg[f].r > seg[f].l) { if (seg[f].who == 0) { seg[f<<1].who = seg[f<<1|1].who = seg[f].who; seg[f].who = -1; } else if (seg[f].who != -1) { m[who][seg[f].who] = 1; seg[f<<1].who = seg[f<<1|1].who = seg[f].who; seg[f].who = -1; } if (r <= mid) modify(f<<1, l, r, who, m); else if (l > mid) modify(f<<1|1, l, r, who, m); else { modify(f<<1, l, mid, who, m); modify(f<<1|1, mid+1, r, who, m); } up(f); } } int main() { map ::iterator it1, it2; int T, M, y1, y2, x, ans; scanf("%d", &T); build(1, 0, 2*MAXN); while (T--) { ans = 0; seg[1].who = 0; scanf("%d", &M); for (int i = 1; i <= M; ++i) { scanf("%d %d %d", &e[i].y1, &e[i].y2, &e[i].x); e[i].y1 <<= 1, e[i].y2 <<= 1; m[i].clear(); } sort(e+1, e+1+M); for (int i = 1; i <= M; ++i) { // printf("%d %d %d\n", e[i].y1, e[i].y2, e[i].x); modify(1, e[i].y1, e[i].y2, i, m); /* for (it = m[i].begin(); it != m[i].end(); ++it) printf(".. %d ", it->first); */ } for(int i = 1; i <= M; ++i) // 扫描整个表 { for(it1 = m[i].begin(); it1 != m[i].end(); ++it1) // 遍历第i条线的可见线段 { int k = it1->first; // 记录与其中的第k条线段可见 for(it2 = m[i].begin(); it2 != m[i].end(); ++it2) // 如果第k条线段与第i条线段有共同的可见线段的话 ans++ { if (m[k].count(it2->first)) ans++; } } } printf("%d\n",ans); } return 0; }
转载于:https://www.cnblogs.com/Lyush/archive/2012/03/08/2385436.html