Pagini recente » Cod sursa (job #723670) | Cod sursa (job #3131346) | Cod sursa (job #2865671) | Cod sursa (job #712559) | Cod sursa (job #163660)
Cod sursa(job #163660)
#include <fstream>
std::ifstream f1("wanted.in");
std::ofstream f2("wanted.out");
struct elem{
int x, y;
}orase[210];
long dist;
int n, poz, i;
void qsort(int jos, int sus);
void rez(int p, int u, int poz);
int pivot(int jos, int sus);
int main()
{
f1>>n;
for (i=0; i<n; i++)
f1>>orase[i].x>>orase[i].y;
qsort(0, n-1);
// if (((n-1)%2)==0)
// poz=(n-1)/2;
// else
// {
// poz=(n-1)/2;
// if (abs(orase[poz].x)>abs(orase[poz+1].x))
// poz++;
// }//else
// dist=abs(orase[poz].x)+abs(orase[poz].y);
poz=n;
rez(0, n-1, poz);
f2<<dist;
return 0;
}//main
void rez(int p, int u, int poz)
{
int t;
if (p==u)
{
dist+=abs(orase[poz].y)+abs(orase[p].x-orase[poz].x)+abs(orase[p].y);
poz=p;
}//if
else
{
if (((p+u)%2)==0)
t=(p+u)/2;
else
{
t=(p+u)/2;
if (abs(orase[t].x)>abs(orase[t+1].x))
t++;
}//else
dist+=abs(orase[poz].y)+abs(orase[t].x-orase[poz].x)+abs(orase[t].y);
poz=t;
if ((poz-p)>(u-poz))
rez(p, poz-1, poz);
else
rez(poz+1, u, poz);
}//else
}//rez
int pivot(int jos, int sus)
{
int i1=jos, i2=sus;
elem t;
while (i1<i2)
{
while ((orase[i1].x<=orase[jos].x)&&(i1<=i2))
i1++;
while ((orase[i2].x>orase[jos].x)&&(i1<=i2))
i2--;
if ((orase[i1].x>orase[i2].x)&&(i1<i2))
{
t=orase[i1];
orase[i1]=orase[i2];
orase[i2]=t;
}//if
}//while
t=orase[i2];
orase[i2]=orase[jos];
orase[jos]=t;
return i2;
}//pivot
void qsort(int jos, int sus)
{
int p;
if (jos<sus)
{
p=pivot(jos, sus);
qsort(jos, p-1);
qsort(p+1, sus);
}//if
}//qsort