概述
题意:给你n条平行x或y轴的线段,保证没有公共端点 没有覆盖,问有多少交点。
思路:对所有线段按x坐标排序,将y坐标离散化,将水平线段拆成两部分,左端点一个,右端点+1一个, 枚举所有线段遇到水平线段的左端点,对应y坐标在树状数组中的值+1,遇到水平线段的(右端点+1)时,将其对应y坐标在树状数组中的值-1.遇到竖直线段时,查询其纵坐标区间的和,也就是条竖直线段能产生的交点的个数.
代码:
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn = 2e5+5;
struct node
{
int type, x, y1, y2;
node() {}
node(int tt, int xx, int yy1, int yy2): type(tt), x(xx), y1(yy1), y2(yy2) {}
bool operator < (const node &a) const
{
if(x == a.x) return type < a.type;
else return x < a.x;
}
}a[maxn];
int Hash[maxn], tree[maxn];
int lowbit(int x)
{
return x&(-x);
}
void update(int pos, int val)
{
while(pos < maxn)
{
tree[pos] += val;
pos += lowbit(pos);
}
}
int query(int pos)
{
int res = 0;
while(pos)
{
res += tree[pos];
pos -= lowbit(pos);
}
return res;
}
int main(void)
{
int _, n, cnt, hash_cnt;
cin >> _;
while(_--)
{
cnt = hash_cnt = 0;
scanf("%d", &n);
for(int i = 1; i <= n; i++)
{
int x1, y1, x2, y2;
scanf("%d%d%d%d", &x1, &y1, &x2, &y2);
if(y1 == y2)
{
if(x1 > x2) swap(x1, x2);
a[cnt++] = node(0, x1, y1, 1);
a[cnt++] = node(0, x2+1, y1, -1);
Hash[hash_cnt++] = y1;
}
else
{
if(y1 > y2) swap(y1, y2);
a[cnt++] = node(1, x1, y1, y2);
Hash[hash_cnt++] = y1;
Hash[hash_cnt++] = y2;
}
}
sort(Hash, Hash+hash_cnt);
int id = 1;
map<int, int> m;
for(int i = 0; i < hash_cnt; i++)
if(!m[Hash[i]])
m[Hash[i]] = id++;
sort(a, a+cnt);
memset(tree, 0, sizeof(tree));
ll ans = 0;
for(int i = 0; i < cnt; i++)
{
if(a[i].type)
ans += query(m[a[i].y2])-query(m[a[i].y1]-1);
else
update(m[a[i].y1], a[i].y2);
}
printf("%lldn", ans);
}
return 0;
}
最后
以上就是专一黑裤为你收集整理的HDU 5862 Counting Intersections(树状数组)的全部内容,希望文章能够帮你解决HDU 5862 Counting Intersections(树状数组)所遇到的程序开发问题。
如果觉得靠谱客网站的内容还不错,欢迎将靠谱客网站推荐给程序员好友。
本图文内容来源于网友提供,作为学习参考使用,或来自网络收集整理,版权属于原作者所有。
发表评论 取消回复