Cod sursa(job #467303)

Utilizator PavelRazvanPavel Razvan PavelRazvan Data 28 iunie 2010 13:59:29
Problema Cadrane Scor 0
Compilator cpp Status done
Runda Stelele Informaticii 2010, clasele X-XII, Ziua 2 Marime 1.49 kb
#include<algorithm>
using namespace std;
#define DIM 100005

struct ok
{
    int x,y;
} a[DIM],b[DIM];
int sol,n;

inline int solve (int x,int y)
{
    int i,s=0;
    if(x==y)
        --s;
    for(i=1;i<=y;++i)
        if(b[i].x>=a[x].x)
            ++s;
    for(i=y;i<=n;++i)
        if(b[i].x<=a[x].x)
            ++s;
    return s;
}

struct cmp1
{
    bool operator() (const ok &a, const ok &b) const
    {
        return a.x<b.x;
    }
};
struct cmp2
{
    bool operator() (const ok &a, const ok &b) const
    {
        return a.y<b.y;
    }
};

char buff[100];
int poz;
inline void pars (int &nr)
{
    nr=0;
    bool smn=0;
    while(buff[poz]<'0' || buff[poz]>'9')
    {
        if(buff[poz]=='-')
            smn=1;
        if(++poz==100)
            fread(buff,1,100,stdin),poz=0;
    }

    while(buff[poz]>='0' && buff[poz]<='9')
    {
        nr=nr*10+buff[poz]-'0';
        if(++poz==100)
            fread(buff,1,100,stdin),poz=0;
    }
    if(smn)
        nr=-nr;
}
int main ()
{
    freopen("cadrane.in","r",stdin);
    freopen("cadrane.out","w",stdout);
    int i,j,sol2;
    pars(n);
    for(i=1;i<=n;++i)
    {
        pars(a[i].x);
        pars(a[i].y);
        b[i]=a[i];
    }
    sort(1+a,1+a+n,cmp1 ());
    sort(1+b,1+b+n,cmp2 ());
    for(i=1;i<=n;++i)
    {
        sol2=1<<30;
        for(j=1;j<=i;++j)
            sol2=min(sol2,solve(i,j));
        sol=max(sol,sol2);
    }
    printf("%d",sol);
    return 0;
}