fafdu1992
BAN USER// no extra memory and less # of swaps compared to other method
void rotate(vector< vector<int> >& a, int n)
{
for (cn=n, i=0; cn>=2 ; cn-=2; i++)
{
int j = cn-1;
for (step=0; step < cn-1; step++)
{
rotate_ele(a[i][i+step], a[i+step][j], a[i+cn-1][j-step], a[i+cn-1-step][i]);
}
}
}
void rotate_ele(int &a, int& b, int& c, int& d)
{
int temp = a;
a = d;
d = c;
c = b;
b = temp;
}
// optimzing on that, no extra memory .
void rotate(vector< vector<int> >& a, int n)
{
for (cn=n, i=0; cn>=2 ; cn-=2; i++)
{
int j = cn-1;
for (step=0; step < cn-1; step++)
{
rotate_ele(a[i][i+step], a[i+step][j], a[i+cn-1][j-step], a[i+cn-1-step][i]);
}
}
}
void rotate_ele(int &a, int& b, int& c, int& d)
{
int temp = a;
a = d;
d = c;
c = b;
b = temp;
}
int quickselect(int a[], int n, int k)
{
assert(n >= k);
if (n==1) return a[0];
int i(0), lt(0), gt(n-1);
int p = median(a[0], a[n/2], a[n-1]);
while (i <= gt) {
if (a[i] == p) i++;
else if (a[i] < p) exch(i++, lt++);
else if (a[i] > p) exch(i, gt--);
}
if (k <= lt) return quickselect(a, lt, k);
if (k <= gt) return a[gt-1];
else return quickselect(a+gt+1, n-gt-1, k-gt-1);
}
int median(int a[], int n)
{
if (n&1) return quickselect(a, n, n/2+1);
else return (quickselect(a, n, n/2+1) + quickselect(a, n, n/2) ) /2.0;
}
double eval(string& s)
- fafdu1992 October 06, 2013{
stringstream strin(s);
while (strin >> word) {
if (is_op(word))
{
double x = s.top(); s.pop();
double y = s.top(); s.pop();
s.push( compute(x, y, word) );
}
else
s.push( atof(word.c_str()) );
}
}
return s.top();