Cod sursa(job #1147932)

Utilizator andrei_diaconuAndrei Diaconu andrei_diaconu Data 20 martie 2014 11:45:13
Problema Pachete Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.2 kb
#include <fstream>
#include <algorithm>
#include <set>
#define NMax 50001
using namespace std;
ifstream f("pachete.in");
ofstream g("pachete.out");
int n, i, nrd, nrn, xp, yp, x, y, c[5];
multiset<int> mult;
multiset<int>::iterator it;
multiset<int>::iterator it2;

struct firma {
    int x;
    int y;
} fi[NMax], f1[NMax], f2[NMax], f3[NMax], f4[NMax];
bool cmp(const firma &f1, const firma &f2)
{
    if (f1.x == f2.x)
        return f1.y < f2.y;
    return f1.x < f2.x;
}
int main()
{
    f>>n>>xp>>yp;
    for (i=1; i<=n; i++) {
        f>>x>>y;
        x-=xp;
        y-=yp;
        fi[i].x=x;
        fi[i].y=y;
    }
    for (i=1; i<=n; i++) {
        if(fi[i].x >= 0 && fi[i].y >=0) {
            f1[++c[1]].x=fi[i].x;
            f1[c[1]].y=fi[i].y;
        }
        else if(fi[i].x >= 0 && fi[i].y < 0) {
            f2[++c[2]].x=fi[i].x;
            f2[c[2]].y=fi[i].y;
        }
        else if(fi[i].x < 0 && fi[i].y < 0) {
            f3[++c[3]].x=fi[i].x;
            f3[c[3]].y=fi[i].y;
        }
        else{
            f2[++c[4]].x=fi[i].x;
            f2[c[4]].y=fi[i].y;
        }
    }
    sort(f1+1, f1+c[1]+1, cmp);
    sort(f2+1, f2+c[2]+1, cmp);
    sort(f3+1, f3+c[3]+1, cmp);
    sort(f4+1, f4+c[4]+1, cmp);
    mult.insert(mult.begin(), f1[1].y);
    nrd=1;
    for (i=2; i<=c[1]; i++) {
        it2=mult.lower_bound(f1[i].y);
        if  (it2!=mult.end())
            mult.erase(it2);
        else
            nrd++;
        mult.insert(f1[i].y);
    }
    mult.clear();
    for (i=2; i<=c[2]; i++) {
        it2=mult.lower_bound(f2[i].y);
        if  (it2!=mult.end())
            mult.erase(it2);
        else
            nrd++;
        mult.insert(f2[i].y);
    }
    mult.clear();
    for (i=2; i<=c[3]; i++) {
        it2=mult.lower_bound(f3[i].y);
        if  (it2!=mult.end())
            mult.erase(it2);
        else
            nrd++;
        mult.insert(f3[i].y);
    }
    mult.clear();
    for (i=2; i<=c[4]; i++) {
        it2=mult.lower_bound(f4[i].y);
        if  (it2!=mult.end())
            mult.erase(it2);
        else
            nrd++;
        mult.insert(f4[i].y);
    }
    g<<nrd;
    return 0;
}