Red and blue points [CodeChef December Challenge 2017 G]

https://www.codechef.com/DEC17/problems/REDBLUE

N個の赤点とM個の青点がある2D平面がある。
この平面に直線を引いて、赤点と青点の2つに分けたい。
赤点と青点の一部を消さないと分けられない時、最小何個消せば分けられるか。

解法

まず愚直解法を考えてみる。
直線を引いて二つに分けるが、適当に引くのではなく、任意の二点を直線で結んだ直線で分ければいい。
これは適当に線を引いても、点と公差するギリギリまで線を移動させてやれば、結果を変えずに任意の二点の上に事実上乗せられるからである。
そのため、部分点解法としては、任意の二点についての直線を引いて、

• 片方の赤点の個数red1,青点の個数blue1、もう片方の赤点の個数red2,青点の個数blue2をカウント
• min(red1+blue2,red2+blue1)がこの直線で区切るときに消す必要がある点の最小値

をしていけばいい。
これだとO((N+M)^3)

これを高速化することでACを取るが、「片方の赤点の個数red1,青点の個数blue1、もう片方の赤点の個数red2,青点の個数blue2をカウント」の部分を尺取り法で高速化していく。
直線を引く前に中心とする点を1つ選び、他の点への偏角を求めておく。
次に偏角を昇順ソートして、この配列を使って尺取法をする。
偏角が小さい方から順に中心と繋いで直線を作っていくが、両側に何個、赤点青点があるかを尺取法でPIだけ偏角が大きい頂点のindexを増やしながら高速にカウントしていく。
これだとO((N+M)^2)でAC

これが同様の考え方を使う類題

const double EPS = 1e-8, INF = 1e12, PI = 2 * acos(0.0);
typedef complex<double> P;
namespace std {
    bool operator < (const P& a, const P& b) { return real(a) != real(b) ? real(a) < real(b) : imag(a) < imag(b); } 
    bool operator == (const P& a, const P& b) { return abs(real(a) - real(b)) < EPS && abs(imag(a) - imag(b)) < EPS; }
    P operator / (const P& a, const double& b) { return P(real(a) / b, imag(a) / b); }
    P operator * (const P& a, const double& b) { return P(real(a) * b, imag(a) * b); }
}
double argument(const P &a, const P &b) { // argument for A->B[-PI,PI]
    double ax = real(a), ay = imag(a), bx = real(b), by = imag(b);
    return atan2(by - ay, bx - ax);
}



int N, M, NN;
vector<pair<P, int>> points;
//---------------------------------------------------------------------------------------------------
void solve() {
    points.clear();

    cin >> N >> M;
    rep(i, 0, N) {
        int x, y; cin >> x >> y;
        points.push_back({ P(x, y), 0 });
    }
    rep(i, 0, M) {
        int x, y; cin >> x >> y;
        points.push_back({ P(x, y), 1 });
    }

    int ans = 10101010;
    NN = N + M;
    rep(i, 0, NN) {
        auto p = points[i].first;
        vector<pair<double, int>> v;
        rep(j, 0, NN) if (i != j) v.push_back({ argument(p, points[j].first), points[j].second });
        sort(v.begin(), v.end());
        rep(j, 0, NN - 1) v.push_back({ v[j].first + 2 * PI, v[j].second });

        int red1 = N, red2 = 0, blue1 = M, blue2 = 0;
        if (points[i].second == 0) red1--;
        else blue1--;

        int k = 0;
        rep(j, 0, NN - 1) {
            while (v[k].first < v[j].first + PI) {
                if (v[k].second == 0) red1--, red2++;
                else blue1--, blue2++;
                k++;
            }
            if (v[j].second == 0) red2--;
            else blue2--;

            int cost = min(red1 + blue2, red2 + blue1);
            ans = min(ans, cost);

            if (v[j].second == 0) red1++;
            else blue1++;

            
        }
    }
    printf("%d\n", ans);
}
//---------------------------------------------------------------------------------------------------
void _main() {
    int T; cin >> T;
    rep(t, 0, T) solve();
}