Cod sursa(job #923503)

Utilizator repp4raduRadu-Andrei Szasz repp4radu Data 23 martie 2013 17:32:25
Problema Balans Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.04 kb
#include <fstream>
#include <vector>
#include <algorithm>
#include <set>

#define MAX 50000
#define x first
#define y second
#define PII pair<int, int>

using namespace std;

int N, M;
vector<PII> V;
set<PII> ans;

void citire() {
    ifstream in("arbsat2.in");
    in>>N>>M;
    for(int i = 1, A, B; i <= N; i++) {
        in>>A>>B;
        V.push_back(make_pair(A, B));
    }
    in.close();
    sort(V.begin(), V.end());
}

void solve(int left, int right) {
    if(right - left < 1) return;
    int mid = (right + left) >> 1, xMid = V[mid].x;
    solve(left, mid);
    solve(mid + 1, right);
    for(int i = left; i <= right; i++)
        ans.insert(make_pair(xMid, V[i].y));
}

void afisare() {
    ofstream out("arbsat2.out");
    for(int i = 0; i < N; i++) ans.erase(V[i]);
    out<<ans.size()<<"\n";
    for(set<PII>::iterator it = ans.begin(); it != ans.end(); ++it)
        out<<(*it).x<<" "<<(*it).y<<"\n";
    out.close();
}

int main() {
    citire();
    solve(0, N - 1);
    afisare();
    return 0;
}