Cod sursa(job #1871877)

Utilizator KOzarmOvidiu Badea KOzarm Data 7 februarie 2017 18:34:27
Problema Pachete Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.28 kb
#include <fstream>
#include <algorithm>
using namespace std;
ifstream fin("pachete.in");
ofstream fout("pachete.out");

struct coord
{
    int i,j,cost;
}O,a[50005],b[50005];

int n,k;


int cost(coord x,coord y)
{
    return abs(x.i-y.i)+abs(x.j-y.j);
}

bool cmp(coord a,coord b)
{
    if(a.i==b.i)
        return a.j<b.j;
    else
        return a.i>b.i;
}

bool verifica(int i,int j)
{
    if(a[i].cost+cost(a[i],b[i])>b[j].cost)
        return 0;
    bool si,sj;
    if(a[i].i>O.i)
        si=1;
    else
        si=0;
    if(b[j].i>O.i)
        sj=1;
    else
        sj=0;
    if(si!=sj)
        return 0;

    if(a[i].j>O.j)
        si=1;
    else
        si=0;
    if(b[j].j>O.j)
        sj=1;
    else
        sj=0;
    if(si!=sj)
        return 0;
    return 1;
}


int main()
{
    fin>>n;
    fin>>O.i>>O.j;
    for(int i=1;i<=n;i++)
    {
        fin>>a[i].i>>a[i].j;
        a[i].cost=cost(a[i],O);
    }
    sort(a+1,a+n+1,cmp);

    for(int i=1;i<=n;i++)
    {
        int j;
        for(j=1;j<=k;j++)
        if(verifica(i,j))
        {
            b[j]=a[i];
            break;
        }
        if(j==k+1)
        {
            k++;
            b[k]=a[i];
        }
    }
    fout<<k;
    return 0;
}