[CF 497D] Gears

作法：

當兩個多邊形碰撞時，一定是一個多邊形的其中一個頂點碰到另一個多邊形的線段，並且顯然當有頂點碰到別人的線段時他們一定相撞了。因此我們只要對兩個多邊形的其中一個枚舉頂點，另一個枚舉邊，然後想辦法$O(1)$判斷這個點會不會跑到這條線段上就可以了。這裡要用相對運動來看會好做很多。假設現在要判斷的是$A$上的一條線段和$B$上的一個頂點$X$是否會在運動的時候碰到，想像站在$P$點看所有東西，並且面對的方向是跟著$A$一起轉的，也就是當$A$順時針旋轉了$\theta$度之後面對的方向也跟著順時針轉$\theta$度，那麼我們看到的$A$上的這條線段會是永遠不動的。設時間$0$時$Q$的座標為$(a,b)$，$X$的座標為$(x,y)$，那麼可以知道$X$被旋轉了$\theta$度之後他在時間$0$的座標系上的座標會是$M_{-\theta}\begin{bmatrix}x-a\\y-b\end{bmatrix}+\begin{bmatrix}a\\ b\end{bmatrix}$，其中$M_{\theta}$代表的是可以將一個點以原點為中心逆時針旋轉$\theta$的矩陣。但此時我們的座標系已經順時針旋轉$\theta$度了，所以這時候看到的$X$點的座標必須要逆時針旋轉$\theta$度才是對的，也就是等於$M_{\theta}(M_{-\theta}\begin{bmatrix}x-a\\y-b\end{bmatrix}+\begin{bmatrix}a\\ b\end{bmatrix})=\begin{bmatrix}x-a\\y-b\end{bmatrix}+M_{\theta}\begin{bmatrix}a\\ b\end{bmatrix}$，由這個式子就可以看出這是一個以$(x-a,y-b)$為圓心，半徑為$\sqrt{a^2+b^2}$的圓了，因此只要寫個線段和圓是否有相交的函式就可以了。

code :

#include<bits/stdc++.h>
#define DB double
using namespace std;
const int maxn=1000+10 ;
 
struct pt
{
    DB x,y;
    void scan(){scanf("%lf%lf",&x,&y) ;}
};
struct cir
{
    DB x,y,r;
    cir(const pt &c,DB _r){x=c.x , y=c.y , r=_r ;}
};
 
const DB eps=1e-7 ;
int dcmp(DB x)
{
    if(fabs(x)<eps) return 0 ;
    else return x>0 ? 1 : -1 ;
}
 
pt operator + (const pt &a,const pt &b) {return (pt){a.x+b.x , a.y+b.y} ; }
pt operator - (const pt &a,const pt &b) {return (pt){a.x-b.x , a.y-b.y} ; }
pt operator * (const pt &a,const DB &d) {return (pt){d*a.x,d*a.y} ; }
DB dot(const pt &a,const pt &b){return a.x*b.x + a.y*b.y ;}
DB cross(const pt &a,const pt &b) {return a.x*b.y - a.y*b.x ;}
DB length(const pt &a) {return sqrt(dot(a,a)) ;}
 
DB pt_to_seg(const pt &p,const pt &a,const pt &b)
{
    return fabs(cross(p-a,b-a))/length(a-b) ;
}
 
pt pt_foot(const pt &p,const pt &a,const pt &b)
{
    return a + (b-a) * (dot(p-a,b-a)/dot(b-a,b-a)) ;
}
 
bool seg_inter_circle(const pt &a,const pt &b,const cir &C)
{
    pt c=(pt){C.x,C.y} ;
    if(dcmp(C.r-length(c-a))>=0 && dcmp(C.r-length(c-b))<=0) return 1 ;
    if(dcmp(C.r-length(c-b))>=0 && dcmp(C.r-length(c-a))<=0) return 1 ;
    if(dcmp(C.r-length(c-b))>0 && dcmp(C.r-length(c-a))>0) return 0 ;
    if(dcmp(pt_to_seg(c,a,b)-C.r)>0) return 0 ;
    pt f=pt_foot(c,a,b) ;
    return dcmp(dot(a-f,b-f))<=0 ;
}
 
pt P,Q,a[maxn],b[maxn] ;
bool check(const pt &p1,const pt &p2,const pt &q)
{
    return seg_inter_circle(p1-P,p2-P,cir(q-Q,length(P-Q))) ;
}
 
int n,m ;
main()
{
    P.scan() ; scanf("%d",&n) ;
    for(int i=0;i<n;i++) a[i].scan() ;
    Q.scan() ; scanf("%d",&m) ;
    for(int i=0;i<m;i++) b[i].scan() ;
    for(int i=0;i<n;i++) for(int j=0;j<m;j++)
        if(check(a[i],a[(i+1)%n],b[j])){printf("YES\n") ; return 0 ;}
    swap(n,m) ; swap(P,Q) ; swap(a,b) ;
    for(int i=0;i<n;i++) for(int j=0;j<m;j++)
        if(check(a[i],a[(i+1)%n],b[j])){printf("YES\n") ; return 0 ;}
    printf("NO\n") ;
}