Circles are POINTS !#13067

Circles are POINTS ! (Editorial)

Hint $1$ : solve the problem for $3$ points only.

Hint $2$ : there are two points which are always present in the set (base points).

Solution: First, for $n = 3$ n = 3 points, we have two cases.

Case $1$ : the points are collinear, so it's impossible to draw a circle that passes through them.

Case $2$ : the points aren't collinear , so they form a triangle, and the center of the circle which passes through them is the intersection of the perpendicular bisectors of the triangle sides , so it's a unique point.

Now for $n$ points $p_{1}, p_{2}, ..., p_{n}$ p_1 , p_2 , ... , p_n.

Suppose we have a circle $C$ which fulfills the condition.

For each $i$ ( $1 \leq i \leq n$ 1 \le i \le n ): $p_{i} \in C$ p_i \in C

If we fixed any two points $p_{j}, p_{k}$ p_j , p_k, we can rewrite the condition as follows:

For each $i$ ( $1 \leq i \leq n$ 1 \le i \le n , $i \neq = j$ i \neq j , $i \neq = k$ i \neq k): ( $p_{j}, p_{k}, p_{i}$ p_j , p_k , p_i) $\in C$ . which is the $3$ points case again.

So circle $C$ exists when:

there are no collinear points with $p_{j}, p_{k}$ p_j , p_k.
$C i r (p_{j}, p_{k}, p_{1}) = C i r (p_{j}, p_{k}, p_{2}) = ... = C i r (p_{j}, p_{k}, p_{n})$ Cir(p_j , p_k , p_1) = Cir(p_j , p_k , p_2) = ... = Cir(p_j , p_k , p_n) where $C i r (a, b, c)$ Cir(a,b,c) is the center of the circle that passes through the three points of the triangle.

But since there are addition and removal queries , we can't choose any two points as fixed points. Since base points $p_{a}, p_{b}$ p_a , p_b are always present in the set , it's optimal to choose them as fixed points.

So to answer the queries , let $ba d$ be the number of collinear triples ( $p_{a}, p_{b}, p_{i}$ p_a , p_b , p_i) , and keep a set containing the circumcenter of triples ( $p_{a}, p_{b}, p_{i}$ p_a , p_b , p_i).

Now when you need to add a point $p$ , if ( $p_{a}, p_{b}, p$ p_a , p_b , p) are collinear, increase $ba d$ by $1$ ; otherwise, add $C i r (p_{i}, p_{j}, p)$ Cir(p_i , p_j , p) to the set.

When you need to remove a point $p$ , decrease $ba d$ by 1 if ( $p_{a}, p_{b}, p$ p_a , p_b , p) are collinear; other wise, remove $C i r (p_{i}, p_{j}, p)$ Cir(p_i , p_j , p) from the set.

The answer is YES when $ba d = 0$ bad = 0 and all points currently in the set are the same; otherwise, answer is NO.

Time Complexity $O ((n + q) \cdot log (n + q))$ \mathcal{O}((n+q)\cdot \text{log}(n+q)).

#include<bits/stdc++.h>
#define endl '\n'
#define int long long
#define F first
#define S second
using namespace std;
const int N = 2e5 + 1;
const int M = 1e9 + 7;
const long double inf = 1e15;
const long double eps = 1e-9;
struct point{
    long double x,y;
    point(){}
    point(long double _x , long double _y)
    {
        x = _x;
        y = _y;
    }
    friend istream &operator>>(istream &is , point &a)
    {
        return is>>a.x>>a.y;
    }
    friend ostream &operator<<(ostream &os , point &a)
    {
        return os<<a.x<<' '<<a.y;
    }
};
struct vec{
    long double a , b;
    vec(){}
    vec(long double _a , long double _b)
    {
        a = _a;
        b = _b;
    }
    vec(point _a , point _b)
    {
        a = _b.x - _a.x;
        b = _b.y - _a.y;
    }
    double operator ^(const vec &v)
    {
        return (a * v.b - b * v.a);
    }
};
struct line{
    long double m , c;
    line(){}
    line(point a,point b)
    {
        if(a.x - b.x == 0){
            m = inf;
            c = a.x;
        }
        else{
            m = (a.y - b.y) / (a.x - b.x);
            c = a.y - m*a.x;
        }
    }
    line(long double _m , point a)
    {
        m = _m;
        if(m == inf)
        c = a.x;
        else
        c = a.y - m * a.x;
    }
    long double get(long double x)
    {
        if(m == inf)
        return inf;
        return m * x + c;
    }
    long double inv()
    {
        if(m == inf)
        return 0;
        if(m == 0)
        return inf;
        return -1/m;
    }
};
point isect(line a , line b)
{
    if(a.m == b.m)
    return point(inf , inf);
    if(a.m == inf)
        return point(a.c , b.get(a.c));
    if(b.m == inf)
        return point(b.c , a.get(b.c));
    long double x,y;
    x = (b.c - a.c) / (a.m - b.m);
    y = a.get(x);
    return point(x , y);
}
point find_circle(point a,point b,point c)
{
    vec abb(a , b) , acc(a , c);
    if((abb ^ acc) == 0)
    return point(inf,inf);
    line ab(a , b) , ac(a , c);
    point p1((a.x + b.x)/2 , (a.y + b.y)/2) , p2((a.x + c.x)/2 , (a.y + c.y)/2);
    long double m1 = ab.inv() , m2 = ac.inv();
    line nab(m1 , p1) , nac(m2 , p2);
    point cr = isect(nab , nac);
    return cr;
}
signed main()
{
    ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    int tc = 1;
    cin>>tc;
    while(tc--)
    {
        int n,q,x,y;
        cin>>n>>q>>x>>y;
        point a[n+1];
        for(int i=1;i<=n;i++)
        {
            cin>>a[i];
        }
        multiset<long double>xx , yy;
        int bad = 0;
        for(int i=1;i<=n;i++)
        {
            if(i == x || i == y)
            continue;
            point cur = find_circle(a[x] , a[y] , a[i]);
            xx.insert(cur.x);
            yy.insert(cur.y);
            if(cur.x == inf && cur.y == inf)
            bad++;
        }
        if(xx.empty() || (((*prev(xx.end()) - *xx.begin()) < eps) && ((*prev(yy.end()) - *yy.begin()) < eps) && !bad))
        cout<<"YES"<<endl;
        else
        cout<<"NO"<<endl;
        while(q--)
        {
            char c;
            point p;
            cin>>c>>p;
            point cur = find_circle(a[x] , a[y] , p);
            if(c == '+')
            {
                xx.insert(cur.x);
                yy.insert(cur.y);
                if(cur.x == inf && cur.y == inf)
                bad++;
            }
            else
            {
                xx.erase(xx.find(cur.x));
                yy.erase(yy.find(cur.y));
                if(cur.x == inf && cur.y == inf)
                bad--;
            }
            if(xx.empty() || (((*prev(xx.end()) - *xx.begin()) < eps) && ((*prev(yy.end()) - *yy.begin()) < eps) && !bad))
            cout<<"YES"<<endl;
            else
            cout<<"NO"<<endl;
        }
    }
}