Cod sursa(job #1275281)

Utilizator catalincraciunCraciun Catalin catalincraciun Data 24 noiembrie 2014 22:55:28
Problema Pachete Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.35 kb
#include <fstream>
#include <algorithm>

using namespace std;
#define nmax 50010
 
ifstream f("pachete.in");
ofstream g("pachete.out"); 

struct punct
{
    int x, y;
} v[nmax];
 
int cmp (const punct &a, const punct &b)
{
    return a.x<b.x;
}
 
int n, X, Y, vx[5][nmax], vy[5][nmax], p[5], l, sol, s[nmax];
 
int search(int a, int b, int x)
{
    int m, r=0;
    while (a<=b)
    {
        m=(a+b)/2;
        if (s[m]<=x) 
        {
            r=m;
            b=m-1;
        } else a=m+1;
    }
    return r;
}
 
void solve()
{
    sort (v+1, v+l+1, cmp);
    int i, h=0, p;
    for (i=1; i<=l; i++)
    {
        p=search(1,h,v[i].y);
        if (!p) 
            s[++h]=v[i].y; else
            s[p]=v[i].y;
    }
    sol+=h;
}
 
int main()
{
    f>>n;
    f>>X>>Y;
    int i, x, y, c=0, j;
    for (i=1; i<=n; i++)
    {
        f>>x>>y;
        if (x>=X && y>Y) c=1; else
        if (x<X && y>=Y) c=2; else
        if (x<=X && y<Y) c=3; else
        if (x>X && y<=Y) c=4;
        p[c]++;
        vx[c][p[c]]=x;
        vy[c][p[c]]=y;
    }
    for (i=1; i<=4; i++)
    {
        l=p[i];
        for (j=1; j<=l; j++) 
        {
            v[j].x=vx[i][j];
            if (v[j].x<X) v[j].x=X-v[j].x;
            v[j].y=vy[i][j];
            if (v[j].y<Y) v[j].y=Y-v[j].y;
        }
        solve();
    }
    g<<sol<<endl;
    
    g.close(); f.close();
    
    return 0;
}