OIG XVII - gon

// https://szkopul.edu.pl/problemset/problem/VM3OLYNfwgJDgCWFruNn7Z6c/site/?key=statement

#include <bits/stdc++.h>

struct Point {
    long long x, y;
    long long u, v;

    bool operator<(const Point& other) const {
        if (u != other.u) return u < other.u;
        return v < other.v;
    }
};

struct DiagInfo {
    int count;
    long long val;
    bool operator>(const DiagInfo& other) const { return count > other.count; }
};

struct Result {
    long long score;
    long long bx, by;
};

std::vector<DiagInfo> get_counts_desc(const std::vector<long long>& vals) {
    if (vals.empty()) return {};
    std::vector<DiagInfo> res;
    int curr = 0;
    for (size_t i = 0; i < vals.size(); ++i) {
        curr++;
        if (i + 1 == vals.size() || vals[i] != vals[i + 1]) {
            res.push_back({curr, vals[i]});
            curr = 0;
        }
    }
    std::sort(res.begin(), res.end(), std::greater<DiagInfo>());
    return res;
}

Result solve_subset(std::vector<Point>& pts) {
    if (pts.empty()) return {-1, 0, 0};

    std::vector<long long> us, vs;
    us.reserve(pts.size());
    vs.reserve(pts.size());

    std::sort(pts.begin(), pts.end());

    for (const auto& p : pts) {
        us.push_back(p.u);
        vs.push_back(p.v);
    }
    std::sort(us.begin(), us.end());
    std::sort(vs.begin(), vs.end());

    auto u_counts = get_counts_desc(us);
    auto v_counts = get_counts_desc(vs);

    long long best_score = -1;
    long long best_u = 0, best_v = 0;

    long long safe_offset = 400000000;
    long long parity = std::abs(pts[0].u) % 2;
    long long safe_coord = safe_offset + parity;

    if (!u_counts.empty()) {
        if (u_counts[0].count > best_score) {
            best_score = u_counts[0].count;
            best_u = u_counts[0].val;
            best_v = safe_coord;
        }
    }
    if (!v_counts.empty()) {
        if (v_counts[0].count > best_score) {
            best_score = v_counts[0].count;
            best_u = safe_coord;
            best_v = v_counts[0].val;
        }
    }

    for (const auto& p : pts) {
        auto range_u = equal_range(us.begin(), us.end(), p.u);
        long long cnt_u = distance(range_u.first, range_u.second);

        auto range_v = equal_range(vs.begin(), vs.end(), p.v);
        long long cnt_v = distance(range_v.first, range_v.second);

        long long current = cnt_u + cnt_v - 2;
        if (current > best_score) {
            best_score = current;
            best_u = p.u;
            best_v = p.v;
        }
    }

    for (const auto& uc : u_counts) {
        if (uc.count + v_counts[0].count <= best_score) break;

        for (const auto& vc : v_counts) {
            long long potential = uc.count + vc.count;

            if (potential <= best_score) break;

            Point candidate = {0, 0, uc.val, vc.val};
            if (!binary_search(pts.begin(), pts.end(), candidate)) {
                best_score = potential;
                best_u = uc.val;
                best_v = vc.val;
                break;
            }
        }
    }

    long long final_x = (best_u + best_v) / 2;
    long long final_y = (best_v - best_u) / 2;
    return {best_score, final_x, final_y};
}

void solve() {
    int n;
    std::cin >> n;

    std::vector<Point> white_pts, black_pts;
    white_pts.reserve(n);
    black_pts.reserve(n);

    for (int i = 0; i < n; i++) {
        long long r, c;
        std::cin >> r >> c;
        Point p;
        p.x = r;
        p.y = c;
        p.u = r - c;
        p.v = r + c;

        if ((r + c) % 2 == 0) {
            white_pts.push_back(p);
        } else {
            black_pts.push_back(p);
        }
    }

    Result resW = solve_subset(white_pts);
    Result resB = solve_subset(black_pts);

    if (resW.score >= resB.score) {
        std::cout << resW.score << "\n";
        std::cout << resW.bx << " " << resW.by << "\n";
    } else {
        std::cout << resB.score << "\n";
        std::cout << resB.bx << " " << resB.by << "\n";
    }
}

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

    solve();

    return 0;
}