Educational Codeforces Round 68 (Rated for Div. 2) E. Count The Rectangles - codeforces, Count, div, educational, rated, rectangles

Topic link

The general idea of the topic is that in a plane rectangular coordinate system, N line segments will be given. The line segments are guaranteed to be parallel to the coordinate axis, and there will be no collinear line segments. Intersection, now I ask how many rectangles these line segments make up

An old question. When I first encountered it, I hesitated because I didn’t know how to deal with rectangle inclusion. Later, it was found that as long as the scanning line is used to consider how many parallel line segments pass through both of them at the same time, all the inclusions can be calculated.

Using the idea of scanning lines: take a line segment as the base, get the end position of the line segment that passes through it, mark the crossing on the tree array, and then process it up and Its parallel line segments, query the interval sum of the area where the two intersect in the tree array, and update the tree array according to the previous end position during the scanning process. Then continue to loop the process based on the line segment. This is the idea of scanning lines, and the complexity is O(n^2 logn), much like the idea of finding the intersection of line segments but scanning it multiple times.

 1 #include 

 2 using  namespace std;

 3

 4 typedef pair<int,int > pii;

 5 const int toadd = 5001;

 6 const int maxn = 10000+1;

 7 vector V[maxn+4] ,H[maxn+4];

 8 int Flick[maxn+4];

 9 vector<int> ter[maxn];

10

11 int lowbit(int x){

12 return x&(-x);

13 }

14

15 void FlickUpdate(int ind,int C){

16 while(ind<=10001){

17 Flick[ind] += C;

18 ind += lowbit(ind);

19 }

20 }

21

22 int FlickQuery(int ind){

23 int ret = 0;

24 while(ind>0){

25 ret += Flick[ind];

26 ind -= lowbit(ind);

27 }

28 return ret;

29 }

30

31 int main(){

32 int n;

33 scanf("%d",&n);

34 for(int i=0;ii) {

35 int x1,y1,x2,y2;

36 scanf("%d%d%d%d",&x1,&y1,&x2,&y2);

37 x1 += toadd ,y1 += toadd ,x2 += toadd ,y2 += toadd;

38 if(x1>x2) swap(x1,x2);

39 if(y1>y2) swap(y1,y2);

40 if(x1 == x2) V[x1].emplace_back(make_pair(y1,y2));

41 else H[y1].emplace_back(make_pair(x1,x2));

42 }

43 long long ans = 0;

44 for(int i=1;i<=maxn;++i ){

45 for(auto heng: H[i]){

46 for(int l = heng.first;l<=heng.second;++l){

47 for(auto zong: V[l])

48 if(zong.first<=i&&zong. second>i) {

49 FlickUpdate(l,1);

50  ter[zong.second].push_back(l);

51 }

52 }

53 for(int j = i+1;j<=maxn;++ j){

54 for(auto heng2: H[j]){

55 int L = max(heng.first,heng2.first);

56 int R = min(heng.second,heng2.second);

57 if(L<=R) {

58 int cnt = FlickQuery(R)-FlickQuery (L-1);

59 // if(cnt) printf("%d %d is %d
",i-toadd,j-toadd,cnt);

60 ans += 1ll*cnt*(cnt-1)/ 2;

61 }

62 }

63 for(auto x: ter[j]){

64 FlickUpdate(x,-1);

65 }

66  ter[j].clear();

67 }

68

69 }

70 }

71 printf("%lld
",ans);

72 return 0;

73 }

View Code

There is also a general way of writing, to find the number of all quadrilaterals composed of line segments . The idea is a bit similar, but instead of scanning, it is for all line segments Numbered, each line segment has a set to record which line segments it intersects with. Consider two sets of a pair of line segments and take the intersection. The size of the intersection is the number of line segments that pass through the two line segments at the same time, which can be used for calculation. And because of the parallel vertical relationship in this topic, it can be bipartite. It only counts a set of parallel line segments, which means that the intersection of line segments and the calculation of the intersection of two sets can be accelerated by bitset, so n ^ 3 has n ^ 2 * n / constant. For details, please see mikeweat’s statement and link in the comment area.

 1 #pragma GCC optimize("O3", "unroll-loops")

 2 #pragma GCC target("avx2")

 3

 4 #include 

 5 using  namespace std;

 6

 7 typedef pair<int, pair<int,int> > segment;

 8 vector V,H;

 9 bool getmask(segment i,segment j){

10 return j.second.first <= i .first && i.first <= j.second.second &&

11 i.second.first <= j.first && j.first<= i .second.second;

12 }

13

14 int main(){

15 int N;

16 scanf("%d",&N);

17 for(int i=0;ii) {

18 int x1,y1,x2,y2;

19 scanf("%d%d%d%d",&x1,&y1,&x2,&y2);

20 if(x1>x2) swap(x1,x2);

21 if(y1>y2) swap(y1,y2);

22 if(x1==x2) V.emplace_back(make_pair(x1,make_pair(y1,y2)));

23 else H.emplace_back(make_pair(y1,make_pair(x1,x2)));

24 }

25 if(H.size()>< span style="color: #000000;">V.size()) swap(H,V);

26 vector5000>> mask( 1*H.size());

27 for(int i = 0;ii){

28 for(int j=0;jj){

29 mask[i][j] = getmask(H[i ],V[j]);

30 // if(mask[i][j]) printf("%d and %d
",H[i].first,V[j].first);

31 }

32 }

33 long long ans = 0ll;

34 for(int i=0;ii){

35 for(int j=i+1;jj){

36 int cnt = (mask[i]& mask[j]).count();

37 // printf("%d and %d cnt: %d
",H[i].first,H[j].first,cnt);

38 ans += 1ll*cnt*(cnt-1)/ 2;

39 }

40 }

41 printf("%lld
",ans);

42 return 0;

43 }

View Code

Open O3 and unroll-loops can be optimized from 1300ms to about 300ms

#pragma GCC optimize(“O3”, “unroll-loops”)
#pragma GCC target(“avx2”)

share picture

 1  #include 

 2 using  namespace std;

 3

 4 typedef pair<int,int > pii;

 5 const int toadd = 5001;

 6 const int maxn = 10000+1;

 7 vector V[maxn+4] ,H[maxn+4];

 8 int Flick[maxn+4];

 9 vector<int> ter[maxn];

10

11 int lowbit(int x){

12 return x&(-x);

13 }

14

15 void FlickUpdate(int ind,int C){

16 while(ind<=10001){

17 Flick[ind] += C;

18 ind += lowbit(ind);

19 }

20 }

21

22 int FlickQuery(int ind){

23 int ret = 0;

24 while(ind>0){

25 ret += Flick[ind];

26 ind -= lowbit(ind);

27 }

28 return ret;

29 }

30

31 int main(){

32 int n;

33 scanf("%d",&n);

34 for(int i=0;ii) {

35 int x1,y1,x2,y2;

36 scanf("%d%d%d%d",&x1,&y1,&x2,&y2);

37 x1 += toadd ,y1 += toadd ,x2 += toadd ,y2 += toadd;

38 if(x1>x2) swap(x1,x2);

39 if(y1>y2) swap(y1,y2);

40 if(x1 == x2) V[x1].emplace_back(make_pair(y1,y2));

41 else H[y1].emplace_back(make_pair(x1,x2));

42 }

43 long long ans = 0;

44 for(int i=1;i<=maxn;++i ){

45 for(auto heng: H[i]){

46 for(int l = heng.first;l<=heng.second;++l){

47 for(auto zong: V[l])

48 if(zong.first<=i&&zong. second>i) {

49 FlickUpdate(l,1);

50  ter[zong.second].push_back(l);

51 }

52 }

53 for(int j = i+1;j<=maxn;++ j){

54 for(auto heng2: H[j]){

55 int L = max(heng.first,heng2.first);

56 int R = min(heng.second,heng2.second);

57 if(L<=R) {

58 int cnt = FlickQuery(R)-FlickQuery (L-1);

59 // if(cnt) printf("%d %d is %d
",i-toadd,j-toadd,cnt);

60 ans += 1ll*cnt*(cnt-1)/ 2;

61 }

62 }

63 for(auto x: ter[j]){

64 FlickUpdate(x,-1);

65 }

66  ter[j].clear();

67 }

68

69 }

70 }

71 printf("%lld
",ans);

72 return 0;

73 }

View Code

 1 #include 

 2 using  namespace std;

 3

 4 typedef pair<int,int > pii;

 5 const int toadd = 5001;

 6 const int maxn = 10000+1;

 7 vector V[maxn+4],H[maxn+4];

 8 int Flick[maxn+4];

 9 vector<int> ter[maxn];

10 

11 int lowbit(int x){

12     return x&(-x);

13 }

14 

15 void FlickUpdate(int ind,int C){

16     while(ind<=10001){

17         Flick[ind] += C;

18         ind += lowbit(ind);

19     }

20 }

21 

22 int FlickQuery(int ind){

23     int ret = 0;

24     while(ind>0){

25         ret += Flick[ind];

26         ind -= lowbit(ind);

27 }

28     return ret;

29 }

30 

31 int main(){

32     int n;

33     scanf("%d",&n);

34     for(int i=0;ii){

35         int x1,y1,x2,y2;

36         scanf("%d%d%d%d",&x1,&y1,&x2,&y2);

37         x1 += toadd ,y1 += toadd ,x2 += toadd ,y2 += toadd;

38         if(x1>x2) swap(x1,x2);

39         if(y1>y2) swap(y1,y2);

40         if(x1 == x2) V[x1].emplace_back(make_pair(y1,y2));

41         else H[y1].emplace_back(make_pair(x1,x2));

42     }

43     long long ans = 0;

44     for(int i=1;i<=maxn;++i){

45         for(auto heng : H[i]){

46             for(int l = heng.first;l<=heng.second;++l){

47                 for(auto zong : V[l])

48                     if(zong.first<=i&&zong.second>i) {

49                         FlickUpdate(l,1);

50                         ter[zong.second].push_back(l);

51                     }

52             }

53             for(int j = i+1;j<=maxn;++j){

54                 for(auto heng2 : H[j]){

55                     int L = max(heng.first,heng2.first);

56                     int R = min(heng.second,heng2.second);

57                     if(L<=R) {

58                         int cnt = FlickQuery(R) - FlickQuery(L-1);

59 //                        if(cnt) printf("%d %d is %d
",i-toadd,j-toadd,cnt);

60                         ans += 1ll*cnt*(cnt-1)/2;

61                     }

62                 }

63                 for(auto x : ter[j]){

64                     FlickUpdate(x,-1);

65                 }

66                 ter[j].clear();

67             }

68 

69         }

70     }

71     printf("%lld
",ans);

72     return 0;

73 }

分享图片

 1 #pragma GCC optimize("O3", "unroll-loops")

 2 #pragma GCC target("avx2")

 3 

 4 #include 

 5 using namespace std;

 6 

 7 typedef pair<int , pair<int,int> > segment;

 8 vector V,H;

 9 bool getmask(segment i,segment j){

10     return j.second.first <= i.first && i.first <= j.second.second &&

11            i.second.first <= j.first && j.first<= i.second.second;

12 }

13

14 int main(){

15     int N;

16     scanf("%d",&N);

17     for(int i=0;ii){

18         int x1,y1,x2,y2;

19         scanf("%d%d%d%d",&x1,&y1,&x2,&y2);

20         if(x1>x2) swap(x1,x2);

21         if(y1>y2) swap(y1,y2);

22         if(x1==x2) V.emplace_back(make_pair(x1,make_pair(y1,y2)));

23         else H.emplace_back(make_pair(y1,make_pair(x1,x2)));

24 }

25     if(H.size()>V.size()) swap(H,V);

26     vector5000> >  mask(1*H.size());

27     for(int i = 0;ii){

28         for(int j=0;jj){

29             mask[i][j] = getmask(H[i],V[j]);

30 //            if(mask[i][j]) printf("%d and %d
",H[i].first,V[j].first);

31         }

32     }

33     long long ans = 0ll;

34     for(int i=0;ii){

35         for(int j=i+1;jj){

36             int cnt = (mask[i]&mask[j]).count();

37 //            printf("%d and %d cnt : %d
",H[i].first,H[j].first,cnt);

38             ans += 1ll*cnt*(cnt-1)/2;

39         }

40     }

41     printf("%lld
",ans);

42     return 0;

43 }

View Code

 1 #pragma GCC optimize("O3", "unroll-loops")

 2 #pragma GCC target("avx2")

 3 

 4 #include 

 5 using namespace std;

 6 

 7 typedef pair<int , pair<int,int> > segment;

 8 vector V,H;

 9 bool getmask(segment i,segment j){

10     return j.second.first <= i.first && i.first <= j.second.second &&

11            i.second.first <= j.first && j.first<= i.second.second;

12 }

13

14 int main(){

15     int N;

16     scanf("%d",&N);

17     for(int i=0;ii){

18         int x1,y1,x2,y2;

19         scanf("%d%d%d%d",&x1,&y1,&x2,&y2);

20         if(x1>x2) swap(x1,x2);

21         if(y1>y2) swap(y1,y2);

22         if(x1==x2) V.emplace_back(make_pair(x1,make_pair(y1,y2)));

23         else H.emplace_back(make_pair(y1,make_pair(x1,x2)));

24 }

25     if(H.size()>V.size()) swap(H,V);

26     vector5000> >  mask(1*H.size());

27     for(int i = 0;ii){

28         for(int j=0;jj){

29             mask[i][j] = getmask(H[i],V[j]);

30 //            if(mask[i][j]) printf("%d and %d
",H[i].first,V[j].first);

31         }

32     }

33     long long ans = 0ll;

34     for(int i=0;ii){

35         for(int j=i+1;jj){

36             int cnt = (mask[i]&mask[j]).count();

37 //            printf("%d and %d cnt : %d
",H[i].first,H[j].first,cnt);

38             ans += 1ll*cnt*(cnt-1)/2;

39         }

40     }

41     printf("%lld
",ans);

42     return 0;

43 }

codeforces, Count, div, educational, rated, rectangles

Leave a Comment Cancel reply