Cod sursa(job #1914940)

Utilizator blackmanta45Andrei blackmanta45 Data 8 martie 2017 19:01:54
Problema Pachete Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.17 kb
#include <fstream>
#include <algorithm>
using namespace std;
ifstream fin ("pachete.in");
ofstream fout ("pachete.out");
int i,j,d,d1,d2,sumx,sol,sumy,n;

struct nev {
    int x;
    int y;
    bool ok=1;
};
nev v[50010];
int cmp (nev a, nev b){
    if(a.x>b.x)
        return 1;
    else
        if(a.x==b.x && a.y>b.y)
            return 1;
    return 0;
}

int main () {
    fin>>n;
    for(i=1;i<=n+1;i++){
        fin>>v[i].x>>v[i].y;
    }
    sort(v+1,v+n+1,cmp);
    for(i=2;i<=n;i++){
        d=0;
        sumy=v[i].y-v[1].y;
        if(sumy<0)
            sumy*=-1;
        d=sumy+v[i].x-v[1].x;
        v[i].ok=0;
        sol++;
        for(j=i+1;j<=n+1;j++){
                if(v[j].ok){
                    sumx=v[j].x-v[i].x;
                    sumy=v[i].y-v[j].y;
                    if(sumy<0)
                        sumy*=-1;
                    d1=sumx+sumy;
                    sumy=v[j].y-v[i].y;
                    if(sumy<0)
                        sumy*=-1;
                    d2=v[j].x-v[1].x+sumy;
                    if(d+d1<d2)
                        d+=d1,v[j].ok=0;;
            }
        }
    }
    fout<<sol;
}