#include <bits/stdc++.h> using namespace std; typedef long long ll; typedef vector<int> vi; typedef vector<vi> vvi; #define all(x) begin(x),end(x) #define rep(i,a,b) for(int i=(a);i<(b);++i) #define sz(x) int(x.size()) typedef complex<double> pt; #define X real() #define Y imag() auto cross(pt a, pt b) { return a.X*b.Y - a.Y*b.X; } auto in(pt a, pt b) { return a.X*b.X + a.Y*b.Y; } const double eps = 1e-10; bool comp(pt a, pt b) { if(abs(a.X-b.X)<=eps) { return a.Y<b.Y; } return a.X<b.X; } auto ccw(pt a, pt b, pt c) { return cross(b-a,c-b); } vector<pt> convexHull(vector<pt> pts) { if (pts.size() <= 1) return pts; sort(all(pts),comp); vector<pt> h(pts.size()+1); int s = 0, t = 0; for(int it = 2; it--; s = --t, reverse(all(pts))) for(pt p : pts) { while(t>=s+2 && ccw(h[t-2],h[t-1],p) <= 0) t--; h[t++] = p; } return {h.begin(),h.begin()+t - (t==2 && h[0] == h[1])}; } double area(vector<pt> pts) { pt prv = pts.back(); double ans=0; for(auto i : pts) { ans+=cross(i,prv); prv=i; } return abs(ans)/2.; } const int N = 20*81; int A[N][N]; int n; vector<pt> E; typedef complex<int> PT; bool inside(PT at){ return at.X >= 0 and at.X < 81*n and at.Y >= 0 and at.Y <= 81*n; } struct node{ ll d; PT at; bool operator<(const node& o) const { return d>o.d; } }; const PT dir4[] = {{0,1},{1,0},{0,-1},{-1,0}}; const ll oo = 1e18; ll di[N][N]; int T=0; bool same(PT a, PT b) { a-=b; return a.X%n==0 and a.Y%n==0; } void dijkstra(PT startoff){ // kleine coordinaat! startoff+=PT{n*40,n*40}; for(int i=0;i<n*81;++i) { for(int j=0;j<n*81;++j) { di[i][j]=oo; } } priority_queue<node> pq; auto push = [&](ll d, PT at) { if(di[at.X][at.Y]>d) { di[at.X][at.Y]=d; pq.push({d,at}); } }; push(0,startoff); while(!pq.empty()) { auto e = pq.top(); pq.pop(); if(e.d!=di[e.at.X][e.at.Y]) continue; if(same(e.at,startoff)) { auto vec = e.at-startoff; if(e.d) { auto res = pt{vec.X,vec.Y}/(double)e.d; E.push_back(res); } } for(auto to : dir4) { to+=e.at; if(inside(to)) { push(e.d+1+abs(A[e.at.X][e.at.Y]-A[to.X][to.Y]), to); } } } } int main() { cin.tie(NULL); cin.sync_with_stdio(false); cin >> n; rep(i,0,n) rep(j,0,n) cin >> A[i][j]; rep(i,0,N) rep(j,0,N) { A[i][j] = A[i%n][j%n]; } rep(i,0,n){ dijkstra({i,i}); dijkstra({i,n-1-i}); } auto res = convexHull(E); cout << setprecision(15) << area(res)*1e40 << '\n'; }