#include #include #define MAX_N 100000 struct L { int diag; int cnt; struct L *next; }; struct L ls[2*MAX_N]; int lsUsed; struct L *hash[2*MAX_N]; int hashMod; #define hash(direction,diag) hash[direction*MAX_N + ((unsigned)diag)%hashMod]; void pushL (int direction, int diag) { struct L **lp = &hash(direction, diag); struct L *l = *lp; while (l && (l->diag != diag) && l->next) { l = l->next; } if (!l) { l = *lp = ls + lsUsed++; l->diag = diag; l->cnt = 0; l->next = NULL; } else if (l->diag != diag) { l->next = ls + lsUsed++; l = l->next; l->diag = diag; l->cnt = 0; l->next = NULL; } l->cnt++; } int main() { int N; while (scanf("%d\n", &N) == 1) { int i; hashMod = (1<<(int)floor(log(N))) - 1; for (i=0; icnt * (l->cnt-1)); l=l->next; } l = hash[i+MAX_N]; while (l) { cnt += (l->cnt * (l->cnt-1)); l=l->next; } } printf("%lf\n", (double)cnt / (N*N)); } return 0; }