G - Intersecting Rectangles Kattis - intersectingrectangles （扫描线）（判断多个矩形相交）

题目链接：

G - Intersecting Rectangles

题目大意：给你n个矩形，每一个矩形给你这个矩形的左下角的坐标和右上角的坐标，然后问你这些矩形会不会相交，如果存在相交的点，输出1，否则输出0。

具体思路：扫描线，我们首先对x进行排序，然后判断当前x直线对应的线段上是否有x已经覆盖，如果已经有就证明存在相交的情况。但是这样会存在多算的情况，所以我们对于每一个矩形的左端点打一个标记，然后右端点再打一个标记，当左端点的时候，先询问，再去更新。对于右端点，先更新，再去询问。

感谢lxw的讲解。

AC代码：

 #include<bits/stdc++.h>

 using namespace std;

 # define ll long long

 const int maxn = 4e5+;

 int tree[maxn<<];

 struct node{

 int y1,y2,x,flag;

 node(){}

 node(int xx,int yy,int zz,int kk){

 y1=xx;

 y2=yy;

 x=zz;

 flag=kk;

 }

 bool friend operator <(node t1,node t2){

 return t1.x<t2.x;

 }

 }q[maxn<<];

 int lowbit(int t){

 return t&(-t);

 }

 int ask(int t){

 int ans=;

 while(t){

 ans+=tree[t];

 t-=lowbit(t);

 }

 return ans;

 }

 void update(int pos,int val){

 while(pos<=4e5+){

 tree[pos]+=val;

 pos+=lowbit(pos);

 }

 }

 vector<int>w;

 int main(){

 int n;

 scanf("%d",&n);

 int x1,y1,x2,y2;

 for(int i=;i<=n;i++){

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

 q[i]=node(y1,y2,x1,);

 q[i+n]=node(y1,y2,x2,-);

 w.push_back(x1);

 w.push_back(x2);

 w.push_back(y1);

 w.push_back(y2);

 }

 sort(w.begin(),w.end());

 sort(q+,q+*n+);

 int k=;

 for(int i=;i<=*n;i++){

 int l=lower_bound(w.begin(),w.end(),q[i].y1)-w.begin()+;

 int r=lower_bound(w.begin(),w.end(),q[i].y2)-w.begin()+;

 if(q[i].flag==){

 if(ask(r)-ask(l)>){

 k=;

 break;

 }

 update(l,);

 update(r,);

 }

 else {

 update(l,-);

 update(r,-);

 if(ask(r)-ask(l)>){

 k=;

 break;

 }

 }

 }

 if(k){

 printf("1\n");

 }

 else {

 printf("0\n");

 }

 return ;

 }

巴特西

G - Intersecting Rectangles Kattis - intersectingrectangles （扫描线）（判断多个矩形相交）

G - Intersecting Rectangles

最新文章

热门文章