题意：4*4个格点，要求一笔从小到大依次经过这16个点。求使用的最小线段数。
暴搜。
考虑任意一条线段一定满足
1.斜率为2个不超过20的整数的比值；2.至少经过1个点。
搜索状态为（当前画到了第几个点，当前所在射线的方向）
转移为：
在这个点转一下方向，
直接画到下一个点。
画到下一个点，中间转一次方向。
#include<bits/stdc++.h>
using namespace std;
#define For(i,n) for(int i=1;i<=n;i++)
#define Fork(i,k,n) for(int i=k;i<=n;i++)
#define Rep(i,n) for(int i=0;i<n;i++)
#define ForD(i,n) for(int i=n;i;i--)
#define ForkD(i,k,n) for(int i=n;i>=k;i--)
#define RepD(i,n) for(int i=n;i>=0;i--)
#define Forp(x) for(int p=Pre[x];p;p=Next[p])
#define Forpiter(x) for(int &p=iter[x];p;p=Next[p])
#define Lson (o<<1)
#define Rson ((o<<1)+1)
#define MEM(a) memset(a,0,sizeof(a));
#define MEMI(a) memset(a,127,sizeof(a));
#define MEMi(a) memset(a,128,sizeof(a));
#define INF (2139062143)
#define F (100000007)
#define pb push_back
#define mp make_pair
#define fi first
#define se second
#define vi vector<int>
#define pi pair<int,int>
#define SI(a) ((a).size())
#define ALL(x) (x).begin(),(x).end()
typedef long long ll;
typedef long double ld;
typedef unsigned long long ull;
ll mul(ll a,ll b){return (a*b)%F;}
ll add(ll a,ll b){return (a+b)%F;}
ll sub(ll a,ll b){return (a-b+llabs(a-b)/F*F+F)%F;}
void upd(ll &a,ll b){a=(a%F+b%F)%F;}
int read()
{
int x=0,f=1; char ch=getchar();
while(!isdigit(ch)) {if (ch=='-') f=-1; ch=getchar();}
while(isdigit(ch)) { x=x*10+ch-'0'; ch=getchar();}
return x*f;
}
ll sqr(ll a){return a*a;}
ld sqr(ld a){return a*a;}
double sqr(double a){return a*a;}
const double eps=1e-10;
int dcmp(double x) {
if (fabs(x)<eps) return 0; else return x<0 ? -1 : 1;
}
ld PI = 3.141592653589793238462643383;
class P{
public:
ll x,y;
P(ll x=0,ll y=0):x(x),y(y){}
friend ll Dot(P A,P B) {return A.x*B.x+A.y*B.y; }
friend P operator- (P A,P B) { return P(A.x-B.x,A.y-B.y); }
friend P operator+ (P A,P B) { return P(A.x+B.x,A.y+B.y); }
friend P operator* (P A,double p) { return P(A.x*p,A.y*p); }
friend P operator/ (P A,double p) { return P(A.x/p,A.y/p); }
friend bool operator< (const P& a,const P& b) {return dcmp(a.x-b.x)<0 ||(dcmp(a.x-b.x)==0&& dcmp(a.y-b.y)<0 );}
P operator-()const {return P(-x,-y);}
};
P read_point() {
P a;
scanf("%lld%lld",&a.x,&a.y);
return a;
}
bool operator==(const P& a,const P& b) {
return a.x==b.x&&a.y==b.y;
}
bool operator!=(const P& a,const P& b) {
return a.x!=b.x||a.y!=b.y;
}
typedef P V;
ll Cross(V A,V B) {return A.x*B.y - A.y*B.x;}
int n=4,a[1000][100];
P p[1000];
bool OnRay(P a,V v,P b){
return (dcmp(Cross(b-a,v))==0 && dcmp(Dot(b-a,v))>=0) ;
}
double x_max=10000;
P c;
bool RayIntesection(P a,V v,P b,V w){
int det=Cross(v,w);
if(dcmp(det)==0) {
if (!OnRay(a,v,b) && !OnRay(b,w,a)) return false;
} else {
int s = Cross(b-a,w), t = Cross(b-a,v);
if (s*det < 0 || t*det < 0) return false;
double ss = double(s)/det;
double cx = a.x+ss*v.x,cy = a.y+ss*v.y;
if (abs(cx) > x_max || abs(cy) > x_max) return false;
}
return true;
}
typedef pair<int,P> state;
int dist[100][100][100];
int main()
{
memset(dist,0x3f3f3f3f,sizeof(dist));
// freopen("c.in","r",stdin);
// freopen("c.out","w",stdout);
For(i,4) {
For(j,4) {
a[i][j]=read();
p[a[i][j]-1]=P(j,-i+5);
}
}
vector<P> vs;
Fork(x,-30,30) Fork(y,-30,30) if(abs(__gcd(x,y))==1) {
vs.pb(P(x,y));
}
deque<state> q;
for(auto v:vs) {
dist[v.x+50][v.y+50][0] = 1;
q.emplace_back(0,v);
}
auto relax = [&] (state s,state t,int len){
if(dist[t.se.x+50][t.se.y+50][t.fi]>dist[s.se.x+50][s.se.y+50][s.fi]+len) {
dist[t.se.x+50][t.se.y+50][t.fi]=dist[s.se.x+50][s.se.y+50][s.fi]+len;
if(!len) q.push_front(t);
else q.push_back(t);
}
};
int ans=1e9+7;
int an[16];
Rep(i,16) an[i]=INF;
while(!q.empty()){
int i; P v;
tie(i,v) = q.front();
q.pop_front();
an[i]=min(an[i],dist[v.x+50][v.y+50][i]);
if (i==15) {
ans=min(ans,dist[v.x+50][v.y+50][i]) ;
continue;
}
for(auto w:vs) {
if (v!=w) {
relax({i,v},{i,w},1); //正好在点i改变方向
}
}
if(OnRay(p[i],v,p[i+1])) {
relax({i,v},{i+1,v},0); //不改变方向
// cerr<<i<<' '<<dist[v.x+50][v.y+50][i+1]<<endl;
}
for(auto w:vs) {
if (v!=w) {
if (!RayIntesection(p[i],v,p[i+1],-w)) continue;
relax({i,v},{i+1,w},1); //在i点延长出去某点改变方向
}
}
}
// Rep(i,16) cerr<<an[i]<<' ';puts("");
cout<<ans<<endl;
return 0;
}