Problem 1298 : Separate Points

keyword

幾何　複素数　回転

概要

平面上に黒の点と白の点が与えられる。黒と白を分断する直線があるかどうか調べる。
原点中心に回転するとx座標だけ比べればよい。誤差の判定とか回転の細かさとか色々気を配る必要があるようです。
けど嘘っぽい解き方だなあ。

#define N 80000

int main(){
    int i,j,n,m;
    double bma,bmi,wma,wmi,ang=PI/N,tmp;
    static double bxs[100], wxs[100], bys[100], wys[100];
    while(scanf("%d%d",&n,&m)){
        if(n==0 && m==0) break;
        REP(i,n)scanf("%lf%lf",bxs+i,bys+i);
        REP(i,m)scanf("%lf%lf",wxs+i,wys+i);
        REP(i,N){
            bma=wma=-1e99;
            bmi=wmi=1e99;
            REP(j,n){
                tmp = cos(ang*i)*bxs[j]-sin(ang*i)*bys[j];
                if(tmp<bmi)bmi=tmp;
                if(tmp>bma)bma=tmp;
            }
            REP(j,m){
                tmp = cos(ang*i)*wxs[j]-sin(ang*i)*wys[j];
                if(bmi<tmp && tmp<bma) goto mark;
                if(tmp<wmi)wmi=tmp;
                if(tmp>wma)wma=tmp;
            }
            if((bma < wmi - EPS) || (wma < bmi - EPS)) break;
            mark:;
        }
        if(i==N)printf("NO\n");
        else printf("YES\n");
    }
    return 0;
}