BaoDGK - Online C++0x Compiler & Debugging Tool

#include<bits/stdc++.h>
using namespace std;

struct Point
{
    int id;
    int x, y;
};

int n;
long long kc;
vector<Point> p;

vector<vector<bool>> adjbt;
int msz = 0;
bool cbt[25];

void sbt(int k, int cursz)
{
    if (k == n)
    {
        msz = max(msz, cursz);
        return;
    }
    sbt(k + 1, cursz);
    bool able = true;
    for (int i = 0; i < k; ++i)
    {
        if (cbt[i] && adjbt[i][k])
        {
            able = false;
            break;
        }
    }
    if (able)
    {
        cbt[k] = true;
        sbt(k + 1, cursz + 1);
        cbt[k] = false;
    }
}

const int MAXN = 10005;
vector<int> adj[MAXN];
int ghep[MAXN];
bool visited[MAXN];
int color[MAXN];

bool dfs(int u)
{
    if (visited[u]) return false;
    visited[u] = true;
    for (int v : adj[u])
    {
        if (ghep[v] < 0 || dfs(ghep[v]))
        {
            ghep[v] = u;
            return true;
        }
    }
    return false;
}
void bfs(int start_node, const vector<Point>& gnode)
{
    color[start_node] = 1;
    queue<int> q;
    q.push(start_node);

    while (!q.empty())
    {
        int u = q.front();
        q.pop();

        for (int v : adj[u])
        {
            if (color[v] == 0)
            {
                color[v] = 3 - color[u];
                q.push(v);
            }
        }
    }
}
int cal(const vector<Point>& gnode)
{
    if (gnode.empty()) return 0;
    for(const auto& p : gnode) color[p.id] = 0;
    for (const auto& p : gnode)
    {
        if (color[p.id] == 0)
        {
            bfs(p.id, gnode);
        }
    }
    vector<int> gru;
    for (const auto& p : gnode)
    {
        if (color[p.id] == 1)
        {
            gru.push_back(p.id);
        }
    }
    int ghepsz = 0;
    memset(ghep, -1, sizeof(ghep));
    for (int u : gru)
    {
        memset(visited, false, sizeof(visited));
        if (dfs(u))
        {
            ghepsz++;
        }
    }
    return ghepsz;
}


int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    if(fopen("cd.inp","r"))
    {
        freopen("cd.inp","r",stdin);
        freopen("cd.out","w",stdout);
    }

    int d_int;
    cin >> n >> d_int;
    kc = (long long)d_int * d_int;
    p.resize(n);
    for (int i = 0; i < n; ++i)
    {
        p[i].id = i;
        cin >> p[i].x >> p[i].y;
    }

    if (n <= 22)
    {
        adjbt.assign(n, vector<bool>(n, false));
        for (int i = 0; i < n; ++i)
        {
            for (int j = i + 1; j < n; ++j)
            {
                long long dx = p[i].x - p[j].x;
                long long dy = p[i].y - p[j].y;
                if (dx * dx + dy * dy == kc)
                {
                    adjbt[i][j] = adjbt[j][i] = true;
                }
            }
        }
        sbt(0, 0);
        cout << n - msz << endl;
    }
    else
    {
        int res = 0;
        if (kc % 2 != 0)
        {
            vector<Point> chan, le;
            for (const auto& p : p)
            {
                adj[p.id].clear();
                if ((p.x + p.y) % 2 == 0) chan.push_back(p);
                else le.push_back(p);
            }
            for (const auto& u : chan)
            {
                for (const auto& v : le)
                {
                    long long dx = u.x - v.x;
                    long long dy = u.y - v.y;
                    if (dx * dx + dy * dy == kc)
                    {
                        adj[u.id].push_back(v.id);
                        adj[v.id].push_back(u.id);
                    }
                }
            }
            res = cal(p);
        }
        else
        {
            vector<Point> chan, le;
            for (const auto& p : p)
            {
                adj[p.id].clear();
                if ((p.x + p.y) % 2 == 0) chan.push_back(p);
                else le.push_back(p);
            }
            for (size_t i = 0; i < chan.size(); ++i)
            {
                for (size_t j = i + 1; j < chan.size(); ++j)
                {
                    Point u = chan[i], v = chan[j];
                    long long dx = u.x - v.x;
                    long long dy = u.y - v.y;
                    if (dx * dx + dy * dy == kc)
                    {
                        adj[u.id].push_back(v.id);
                        adj[v.id].push_back(u.id);
                    }
                }
            }
            res += cal(chan);
            for (size_t i = 0; i < le.size(); ++i)
            {
                for (size_t j = i + 1; j < le.size(); ++j)
                {
                    Point u = le[i], v = le[j];
                    long long dx = u.x - v.x;
                    long long dy = u.y - v.y;
                    if (dx * dx + dy * dy == kc)
                    {
                        adj[u.id].push_back(v.id);
                        adj[v.id].push_back(u.id);
                    }
                }
            }
            res += cal(le);
        }
        cout << res << endl;
    }
    return 0;
}