poj 3168 Barn Expansion 平面扫描+线段相交问题-白红宇

poj 3168 Barn Expansion 平面扫描+线段相交问题

阅读量：4114 次

发布时间：2019-05-25

本文共 2606 字，大约阅读时间需要 8 分钟。

题意：给你n个矩形，矩形之间只能是完全隔离或者刚好接触，且没有嵌套关系，判断这些矩形中不与

其他任何矩形相接触的个数

ac代码：

#include 
     
       #include 
      
        #include 
       
         #include 
        
          #include 
         
           #include 
          
            #include 
           
             #include 
             #include 
             
               #include 
              
                using namespace std; #define MM(a) memset(a,0,sizeof(a)) typedef long long ll; typedef unsigned long long ULL; const int mod = 1000000007; const double eps = 1e-10; const int inf = 0x3f3f3f3f; const int big=50000; int max(int a,int b) { return a>b?a:b;}; int min(int a,int b) { return a
               
                =ex[j].y1) { ex[j].y2=max(ex[j].y2,ex[i].y2); return 1; } return 0; } int jiaoy(int i,int j) { //printf("//4\n"); if(ey[i].y==ey[j].y&&ey[i].x2>=ey[j].x1) { ey[j].x2=max(ey[j].x2,ey[i].x2); return 1; } return 0; } void solve() { memset(used,0,sizeof(used)); sort(ex+1,ex+2*n+1,cmpx); sort(ey+1,ey+2*n+1,cmpy); for(int i=1;i<=2*n-1;i++) if(jiaox(i,i+1)) used[ex[i].id]=used[ex[i+1].id]=1; for(int i=1;i<=2*n-1;i++) if(jiaoy(i,i+1)) used[ey[i].id]=used[ey[i+1].id]=1; //printf("//2\n"); int res=0; for(int i=1;i<=n;i++) if(!used[i]) res++; printf("%d\n",res); } int main() { while(~scanf("%d",&n)) { for(int i=1;i<=n;i++) { scanf("%d %d %d %d",&a1,&b1,&a2,&b2); add_edgex(i); add_edgey(i); } solve(); } return 0; }

题目分析:从x和y方向两个方向进行拆边就好，分两个方向进行判断，但是注意下面wa的代码错就错在

自己没有考虑到[1,10] [2,5] [7,9]这个情况，因为第一个区间可以完全覆盖第二个区间甚至直接与第三个区间相交

而此时第二哥区间则并没有与第三个区间相交；

#include 
     
       #include 
      
        #include 
       
         #include 
        
          #include 
         
           #include 
          
            #include 
           
             #include 
             #include 
             
               #include 
              
                using namespace std; #define MM(a) memset(a,0,sizeof(a)) typedef long long ll; typedef unsigned long long ULL; const int mod = 1000000007; const double eps = 1e-10; const int inf = 0x3f3f3f3f; const int big=50000; int max(int a,int b) { return a>b?a:b;}; int min(int a,int b) { return a
               
                =ex[j].y1&&ex[i].y1<=ex[j].y2) return 1; return 0; } int jiaoy(int i,int j) { //printf("//4\n"); if(ey[i].y==ey[j].y&&ey[i].x2>=ey[i+1].x1&&ey[i].x1<=ey[j].x2) return 1; return 0; } void solve() { memset(num,0,sizeof(num)); sort(ex,ex+2*cnt+1,cmpx); sort(ey,ey+2*cnt+1,cmpy); for(int i=1;i<=2*cnt-1;i++) if(jiaox(i,i+1)) { num[ex[i].id]--; num[ex[i+1].id]--; } for(int i=1;i<=2*cnt-1;i++) if(jiaoy(i,i+1)) { num[ey[i].id]--; num[ey[i+1].id]--; //printf("//2\n"); } } void ans() { int res=0; for(int i=1;i<=n;i++) if(num[i]>=0) res++; printf("%d\n",res); } int main() { while(~scanf("%d",&n)) { cnt=0; for(int i=1;i<=n;i++) { scanf("%d %d %d %d",&a1,&b1,&a2,&b2); add_edgex(++cnt); add_edgey(cnt); } solve(); ans(); } return 0; }