ecircle.cpp

#include <iostream>
#include <utility>

#define X first
#define Y second

using namespace std;

typedef pair<double, double> pdd;
typedef pair<pdd, double> pcr;

//returns pair of center coords and radius^2
pcr makeCircle(double *nx, double *ny, int n);

int main(){

    int n, m;

    cin >> n >> m;

    double *nx = new double[n];
    double *ny = new double[n];
    double *mx = new double[m];
    double *my = new double[m];
    for (int i = 0; i < n; i++){
        cin >> nx[i] >> ny[i];
    }
    for (int i = 0; i < m; i++){
        cin >> mx[i] >> my[i];
    }

    if (n < 2 || m < 2){
        cout << "YES" << endl;
        return 0;
    }

    //get the first circle
    pcr ncir = makeCircle(nx, ny, n);
    double cx, cy, rsqr, tmpr;
    //remains true if all of "m" coords are outside of the circle
    bool success = true;
    //just renaming for convenience
    cx = ncir.first.X;
    cy = ncir.first.Y;
    rsqr = ncir.second;
    for (int i = 0; i < m; i++){
        //calculating distance^2 between m[i] and center of n_circle
        tmpr = (mx[i] - cx) * (mx[i] - cx) + (my[i] - cy) * (my[i] - cy);
        //if that distance is lesser than the radius of the n_circle, try with another circle
        if (tmpr <= rsqr){
            success = false;
            break;
        }
    }
    //if success == true then all of the "m" dots are outside of the n_circle
    if (success)
        cout << "YES" << endl;
    else{
        //get the second circle
        pcr mcir = makeCircle(mx, my, m);
        //renaming again
        cx = mcir.first.X;
        cy = mcir.first.Y;
        rsqr = mcir.second;
        //set success to true just like in previous case
        success = true;
        for (int i = 0; i < n; i++){
            tmpr = (nx[i] - cx) * (nx[i] - cx) + (ny[i] - cy) * (ny[i] - cy);
            if (tmpr <= rsqr){
                cout << "NO" << endl;
                success = false;
                break;
            }
        }
        if (success)
            cout << "YES" << endl;
    }

    delete [] nx;
    delete [] ny;
    delete [] mx;
    delete [] my;

    return 0;
}

pcr makeCircle(double *nx, double *ny, int n){
    if (n < 2){
        return pcr(pdd(nx[0], ny[0]), 0);
    }
    double max;
    int maxa, maxb;
    //find two points a, b : distance(a,b) is maximal
    for (int i = 0; i < n - 1; i++){
        double tmp;
        for (int j = i + 1; j < n; j++){
            tmp = (nx[i] - nx[j]) * (nx[i] - nx[j]) + (ny[i] - ny[j]) * (ny[i] - ny[j]);
            if (tmp > max){
                max = tmp;
                maxa = i;
                maxb = j;
            }
        }
    }

    double cx, cy, ax, ay, bx, by;
    //renaming for convenience
    ax = nx[maxa];
    ay = ny[maxa];
    bx = nx[maxb];
    by = ny[maxb];
    //center of the circle
    cx = (ax + bx) / 2.;
    cy = (ay + by) / 2.;
    //radius^2
    double rsqr = (ax - cx) * (ax - cx) + (ay - cy) * (ay - cy);
    max = 0;
    int max2;
    //find dot N : distance((cx, cy), N) is maximal
    for (int i = 0; i < n; i++){
        double tmpr;
        tmpr = (nx[i] - cx) * (nx[i] - cx) + (ny[i] - cy) * (ny[i] - cy);
        if (tmpr > max){
            max = tmpr;
            max2 = i;
        }
    }
    //renaming
    double x, y;
    x = nx[max2];
    y = ny[max2];
    //if new dot lies outside of the radius, remake the circle
    if (max > rsqr){
        if (ax == bx){
            //vertical
            cx = (ax * ax + ay * ay - y * y - x * x + 2 * cy * (y - ay)) / (2. * (ax - x));
        }else if(ay == by){
            //horizontal
            cy = (-ax * ax - ay * ay + y * y + x * x + 2 * cx * (x - ax)) / (2. * (y - ay));
        }else{
            double k, b;
            k = -1 / ((ay - by) / (ax - bx));
            b = cy - cx * k;
            // (x - cx)^2 + (y - cy)^2 == (ax - cx)^2 + (ay - cy) ^ 2
            // cy == k * сx + b
            cx = (ax * ax + ay * ay - y * y - x * x - 2 * (ay - y) * b) / (2. * (ax - x + k * (ay - y)));
            cy = cx * k + b;
            rsqr = (ax - cx) * (ax - cx) + (ay - cy) * (ay - cy);
        }
    }

    return pcr(pdd(cx, cy), rsqr);
}