Cod sursa(job #1148114)

Utilizator andrei_diaconuAndrei Diaconu andrei_diaconu Data 20 martie 2014 14:28:09
Problema Pachete Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.51 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];
int dx[]={0, 1, -1, -1, 1}, dy[]={0, 1, 1, -1, -1};
multiset<int> mult;
multiset<int>::iterator it;
multiset<int>::iterator it2;
int semn(int x)
{
    if (x<0)
        return -1;
        return 1;
}
int abs(int x)
{
    if(x<0)
      return -x;
    return x;
}
struct firma {
    int x;
    int y;
} fi[NMax], f1[NMax], f2[NMax], f3[NMax], f4[NMax];
bool cmp(const firma &f1, const firma &f2)
{

    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 ( int cd=1; cd<=4; cd++){
        mult.clear();
        int k=0;
    for (i=1; i<=n; i++) {
         if(semn(fi[i].x)==dx[cd] && semn(fi[i].y)==dy[cd]) {
            f1[++k]=fi[i];
            if (f1[k].x<0)
                f1[k].x=-f1[k].x;
                   if (f1[k].y<0)
                f1[k].y=-f1[k].y;
         }
    }
    sort(f1+1, f1+k+1, cmp);
         if (k>0) {
            nrd++;
            mult.insert(f1[1].y);
         }
    for (i=2; i<=k; i++) {
        it2=mult.upper_bound(f1[i].y);
        if  (it2!=mult.begin()){
         it2--;
            mult.erase(it2);
        }
        else
            nrd++;
        mult.insert(f1[i].y);
    }

    }


    g<<nrd;
    return 0;
}