gistfile1.txt

#ifndef FIXED_H
#define FIXED_H

typedef int64_t fixed_t;
static const fixed_t fixed_precision = 20ll;
static const fixed_t fixed_one = 1ll<<fixed_precision;
static const fixed_t fixed_half = 1ll<<(fixed_precision-1);
static const double fixed_factor = fixed_one;
static const double fixed_inverse_factor = 1.0/fixed_factor;

static double fixed_to_double(fixed_t a) {
    return a*fixed_inverse_factor;
}
static fixed_t fixed_from_double(double a) {
    return round(a*fixed_factor);
}
static int fixed_to_int(fixed_t a) {
    return a>>fixed_precision;
}
static fixed_t fixed_from_int(int a) {
    return a<<fixed_precision;
}

static fixed_t fixed_fract(fixed_t a) {
    return a&(fixed_one-1);
}
static fixed_t fixed_floor(fixed_t a) {
    return a&(~(fixed_one-1));
}
static fixed_t fixed_abs(fixed_t a) {
    return labs(a);
}
static fixed_t fixed_saturate(fixed_t a) {
    return a<0 ? 0 : (a>fixed_one ? fixed_one : a );
}

static fixed_t fixed_mul(fixed_t a, fixed_t b) {
    fixed_t tmp = (a*b);
    tmp >>= (fixed_precision-1ll);
    tmp += tmp&1ll;
    return tmp>>1ll;
}
static fixed_t fixed_div(fixed_t a, fixed_t b) {
    return (a<<fixed_precision)/b;
}
static fixed_t fixed_sqrt(fixed_t a) {
    fixed_t hi = a>fixed_one ? a : fixed_one;
    fixed_t lo = a>fixed_one ? fixed_one : a;
    fixed_t a2 = a << fixed_precision;
    while(hi-lo>1) {
        fixed_t mid = (hi+lo) >> 1;
        if(mid*mid < a2) {
            lo = mid;
        } else {
            hi = mid;
        }
    }
    return (hi*hi-a2)<(a2-lo*lo) ? hi : lo;
}

#endif