Pagini recente » Cod sursa (job #572252) | Cod sursa (job #38299) | Cod sursa (job #3225959) | Cod sursa (job #1100288) | Cod sursa (job #35651)
Cod sursa(job #35651)
#include<stdio.h>
#include<vector>
#include<algorithm>
#include<iostream>
using namespace std;
long int x0;
long int y0;
struct punct
{
long x;
long y;
};
inline unsigned long mdl(long x)
{
if(x<0) return -x;
else
return x;
}
inline int interval(long lx,long ly,long x)
{
if(lx<=ly)
if((x>=lx)&&(x<=ly))
return 1;
else
return 0;
if(lx>ly)
if((x>=ly)&&(x<=lx))
return 1;
else
return 0;
}
//functie de sortare
inline int sort_manhattan(punct p1,punct p2)
{
unsigned long d1;
unsigned long d2;
d1=mdl(x0-p1.x)+mdl(y0-p1.y);
d2=mdl(x0-p2.x)+mdl(y0-p2.y);
return (d1<d2);
}
//functie de semn
inline int sign(unsigned long x)
{
if(x<0) return -1;
if(x>=0) return 1;
};
int main(void)
{
FILE *f;
unsigned int n;
unsigned int i;
unsigned int j;
unsigned long dmax;
unsigned int pmax;
vector< punct > v;
vector< punct >::iterator it;
vector< unsigned int > vt;
unsigned int vd[50000];
unsigned int vtata[50000];
long int drumuri=0;
unsigned int pas;
punct p;
int sx;int sy;
//citeste datele
f=fopen("pachete.in","rt");
fscanf(f,"%d",&n);
fscanf(f,"%ld %ld",&x0,&y0);
for(i=0;i<n;i++)
{
fscanf(f,"%ld %ld",&p.x,&p.y);
v.push_back(p);
}
fclose(f);
dmax=0;
pmax=50001;
//sorteaza nodurile in ordinea distantei manhattan
stable_sort(v.begin(),v.end(),sort_manhattan);
//cat timp mai sunt puncte de procesat
while(v.size()>0)
{
//face un drum nou
drumuri+=1;
//afla cel mai indeparat punct de radacina
pmax=v.size()-1;
//face semnele pe cele 2 axe
sx=v[pmax].x-x0;
sy=v[pmax].y-y0;
//pune intr-un vector temporar doar nodurile din dreptunghiul
//format de radacina cu pmax
vt.clear();
for(i=0;i<v.size();i++)
if(interval(x0,v[pmax].x,v[i].x)&&interval(y0,v[pmax].y,v[i].y))
vt.push_back(i);
//afiseaza vt
// cout<<"vt:";
// for(i=0;i<vt.size();i++)
// cout<<vt[i]<<"|";
// cin>>i;
//afla numarul maxim de noduri ce poate fi pus pe drumul dintre radacina si pmin
//complexitate n patrat
for(i=0;i<vt.size();i++)
vd[i]=0;
vd[0]=1;
vtata[0]=50001;
for(i=1;i<vt.size();i++)
{
vd[i]=1; //distanta de la el direct la radacina
vtata[i]=50001;
for(j=0;j<i;j++) //ia toate nodurie dinaintea lui
//vede daca nodul j se afla inaintea lui i geometric
if((sign(v[i].x-v[j].x)==sign(sx))&&(sign(v[i].y-v[j].y)==sign(sy)))
{
vd[i]=vd[j]+1;
vtata[i]=j;
}
}
//afiseaza vd
// cout<<"vd:";
// for(i=0;i<vt.size();i++)
// cout<<vd[i]<<"|";
// cout<<endl<<"vtata:";
// for(i=0;i<vt.size();i++)
// cout<<vtata[i]<<"|";
// cin>>i;
//sterge nodurile care au fost selectate
j=vt.size()-1;
pas=0;
while(j!=50001)
{
//sterge nodul j
it=v.begin();
it+=vt[j]-pas;
v.erase(it);
// cout<<"-------";
// cout<<"j="<<vt[j]<<endl;
// cout<<(*it).x<<" "<<(*it).y<<"|";
// cout<<endl;
// for(i=0;i<v.size();i++)
// cout<<v[i].x<<" "<<v[i].y<<"|";
// cin>>i;
pas+=1;
j=vtata[j];
// cout<<"Jnou="<<j<<endl;
}
}
//afiseaza solutia
f=fopen("pachete.out","wt");
fprintf(f,"%ld\n",drumuri);
fclose(f);
//sf
return 0;
};