我是靠谱客的博主 负责嚓茶,这篇文章主要介绍HDU-5862-Counting Intersections(树状数组+离散化+扫描线),现在分享给大家,希望可以做个参考。

链接:http://acm.split.hdu.edu.cn/showproblem.php?pid=5862

题意:给出与坐标轴平行的线段,求所有线段的交点个数

题解:先将数据离散化,将两类线段分开存放;考虑横向线段的左右端点,将y值计数,只需将竖向线段扫描一遍,统计y1与y2之间的线段个数,维护bit就好。

CODE:

复制代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
#include <bits/stdc++.h> //#pragma comment(linker, "/STACK:1024000000,1024000000") using namespace std; #define INF 0x3f3f3f3f #define LL long long #define bug cout<<"bug"<<endl const int MAXN = 500007; const int MOD = 1e9 + 9; struct Line { int x1,x2,y1,y2; } line[MAXN],l[MAXN]; struct Node { int x,y,flag; } v[MAXN]; bool cmp1(Line a, Line b) { return a.x1 < b.x1; } bool cmp2(Node a, Node b) { if(a.x!=b.x)return a.x<b.x; return a.flag<b.flag; } int n; vector<int> p; long long sum[MAXN]; void add(int i, int x) { while(i<=MAXN) { sum[i]+=x; i+=i&-i; } } long long get_sum(int i) { long long ans=0; while(i>0) { ans+=sum[i]; i-=i&-i; } return ans; } int main() { int T; scanf("%d",&T); while(T--) { p.clear(); int x1,x2,y1,y2; scanf("%d",&n); int cnt1=0,cnt2=0; for(int i=0; i<n; ++i) { scanf("%d%d%d%d",&line[i].x1,&line[i].y1,&line[i].x2,&line[i].y2); if(line[i].x1>line[i].x2)swap(line[i].x1,line[i].x2); if(line[i].y1>line[i].y2)swap(line[i].y1,line[i].y2); p.push_back(line[i].x1); p.push_back(line[i].x2); p.push_back(line[i].y1); p.push_back(line[i].y2); } sort(p.begin(),p.end()); p.resize(unique(p.begin(),p.end())-p.begin()); for(int i=0; i<n; ++i) { x1=lower_bound(p.begin(),p.end(),line[i].x1)-p.begin()+1; x2=lower_bound(p.begin(),p.end(),line[i].x2)-p.begin()+1; y1=lower_bound(p.begin(),p.end(),line[i].y1)-p.begin()+1; y2=lower_bound(p.begin(),p.end(),line[i].y2)-p.begin()+1; if(x1==x2)l[cnt1++]=Line{x1,x2,y1,y2}; else { v[cnt2].flag=0; v[cnt2].x=x1; v[cnt2++].y=y1; v[cnt2].flag=1; v[cnt2].x=x2; v[cnt2++].y=y2; } } memset(sum,0,sizeof(sum)); sort(l,l+cnt1,cmp1); sort(v,v+cnt2,cmp2); long long ans=0; for(int i=0,j=0; i<cnt1; ++i) { while(j<cnt2 && (v[j].x<l[i].x1 ||(v[j].x==l[i].x1 && v[j].flag==0))) { if(v[j].flag==0)add(v[j].y,1); else add(v[j].y,-1); j++; } ans+=get_sum(l[i].y2)-get_sum(l[i].y1-1); } printf("%I64dn",ans); } return 0; } /* 2 4 1 0 1 3 2 0 2 3 0 1 3 1 0 2 3 2 4 0 0 2 0 3 0 3 2 3 3 1 3 0 3 0 2 */


最后

以上就是负责嚓茶最近收集整理的关于HDU-5862-Counting Intersections(树状数组+离散化+扫描线)的全部内容,更多相关HDU-5862-Counting内容请搜索靠谱客的其他文章。

本图文内容来源于网友提供,作为学习参考使用,或来自网络收集整理,版权属于原作者所有。
点赞(125)

评论列表共有 0 条评论

立即
投稿
返回
顶部