Cod sursa(job #473435)

Utilizator eudanipEugenie Daniel Posdarascu eudanip Data 29 iulie 2010 13:52:39
Problema Pachete Scor 10
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.19 kb
#include<stdio.h>
#include<algorithm>
using namespace std;

int next[50006],n;
int sol,viz[50006];

struct point
{
    int x,y,z;
};
point v[50006],p;

int cmp(const point& a,const point& b)
{
    return (a.z<b.z);
}

int dist(point a,point b)
{
    int l1=a.x-b.x,l2=a.y-b.y;
    if(l1<0)
        l1*=-1;
    if(l2<0)
        l2*=-1;
    return l1+l2;
}

int main ()
{
    int i,j,jp;
    freopen("pachete.in","r",stdin);
    freopen("pachete.out","w",stdout);
    scanf("%d",&n);
    scanf("%d%d",&p.x,&p.y);
    for(i=1;i<=n;i++)
    {
        scanf("%d%d",&v[i].x,&v[i].y);
        v[i].z=dist(p,v[i]);
    }
    sort(v+1,v+n+1,cmp);
    for(i=1;i<=n;i++)
        next[i]=i-1;
    for(i=n;i>=1;i--)
    {
        if(!viz[i])
            sol++;
        jp=i;
        for(j=next[i];j;j=next[j])
        {
            if(viz[j])
            {
                next[jp]=next[j];
                continue;
            }
            if(dist(v[i],v[j])+v[j].z==v[i].z)
            {
                viz[j]=1;
                next[jp]=next[j];
                break;
            }
            jp=j;
        }
    }
    printf("%d\n",sol);
    return 0;
}