codeforces 993 A-白红宇

codeforces 993 A

阅读量：4549 次

发布时间：2019-06-08

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

codeforces 993 A

introduction

判断两个正方形是否相交(只有一个有公共点也算相交)，其中一个平放，另一个倾斜45°。

method

方法有很多，从直观上都可以理解。但我的方法太麻烦了，失败了。

觉得题解的思路很好，所以记录一下。

为了便于描述，平放的正方形记为A，倾斜45°的记为B

相交可以分为4种情况:

B的角落在A中

A的角落在B中

B的中心落在A中

A的中心落在B中

第一种情况好判断，按照是两个平放的正方形来处理。难点是A在B中的情况。

一个想法是将A旋转45°，B也旋转45°，这样就转化成第一种情况。但是这样做的代价是引入了浮点数。题解的巧妙之处就是观察到了放缩是不会改变相交性的。

replace each ? coordinate with ?+? and each ? coordinate with ?−?

这样就完全转化成第一种情况

其他的思路

点都是整点，并且每个正方形最多是100×100，可以枚举两个正方形是否有公共点

tips

放缩是不会改变相交性的

两个平放正方形的相交性

reference

code

#include
    
     #include
     
      #include
      
       #include
       
        #include
        
         #include
         
          #include
          
           #include
           
            #include
            #include
             
              #define DEBUG(x) cout<<#x<<" = "<
              
               <
               
                >(istream &in,square &s) { for(int i=0;i<4 ;i++ ){ in>>s.x[i]>>s.y[i]; if(i==0)s.mxx=s.mix=s.x[i],s.mxy=s.miy=s.y[i]; else { s.mxx=max(s.mxx,s.x[i]); s.mix=min(s.mix,s.x[i]); s.mxy=max(s.mxy,s.y[i]); s.miy=min(s.miy,s.y[i]); } } return in; } friend ostream & operator<<(ostream &out,square &s) { for(int i=0;i<4 ;i++ ){ out<
                
                 <<" "<
                 
                  <<" "; } }};square roughrotate(square s){ square rt; for(int i=0;i<4 ;i++ ){ rt.x[i]=s.x[i]+s.y[i]; rt.y[i]=s.x[i]-s.y[i]; if(i==0)rt.mxx=rt.mix=rt.x[i],rt.mxy=rt.miy=rt.y[i]; else { rt.mxx=max(rt.mxx,rt.x[i]); rt.mix=min(rt.mix,rt.x[i]); rt.mxy=max(rt.mxy,rt.y[i]); rt.miy=min(rt.miy,rt.y[i]); } } return rt;}bool isin(square p,square d){ for(int i=0;i<4 ;i++ ){ if(d.x[i]>=p.mix&&d.x[i]<=p.mxx &&d.y[i]>=p.miy&&d.y[i]<=p.mxy)return true; } int mdx=(d.mix+d.mxx)/2, mdy=(d.miy+d.mxy)/2; if(mdx>=p.mix&&mdx<=p.mxx&&mdy>=p.miy&&mdy<=p.mxy)return true; return false;}int main(){// freopen("in.txt","r",stdin); square par,deg; cin>>par>>deg; bool b1=isin(par,deg); square par1=roughrotate(deg); square deg1=roughrotate(par); bool b2=isin(par1,deg1); if(b1||b2)cout<<"YES"<