masterpiece002_CU_MEMORIE_REDUSA

#include <cstdio>
#include <iostream>
#include <cmath>
#define Dmax 505050
using namespace std;
float T[Dmax]; /// Ar mai fi o solutie, sa-l impart si pe acesta in 2
/// Sa pun partea intreaga intrun short int si partea zecimala in alt short int
/// As reduce memoria pentru T la jumatate. Dar trebuie sa fac si o functie pentru comparare
/// Cred ca asta e. Se reduce memoria la sub 2,5M. Doar ultimul test consuma foarte multa memorie
unsigned short readInt() /// Citirea numerelor intregi prin parsare
{
    bool semn=false;
    unsigned short raspuns=0;
    char c;
    while(true)
    {
        c=getchar();
        if(c==EOF)
            return 1001;
        if(c=='-')
        {
            semn=true;
            break;
        }
        if(c>='0'&&c<='9')
        {
            raspuns=c-'0';
            break;
        }
    }
    while(true)
    {
        c=getchar();
        if(c<'0'||c>'9')
            break;
        raspuns=10*raspuns+c-'0';
    }
    if(semn)
        return -raspuns;
    return raspuns;
}

int main()
{
    int n=0; /// n=nr de segmente simple
    unsigned short X1,Y1,X2,Y2,a,b,r;
    bool SF_FIS=false;
    freopen("masterpiece002.in", "r",stdin);
    while(!SF_FIS)
    {
        X1=readInt();
        if(X1==1001)
        {
            SF_FIS=true;
            break;
        }
        Y1=readInt();X2=readInt();Y2=readInt();
        a=abs(X2-X1),b=abs(Y2-Y1); /// a=latura orizontala si b=latura verticala ale triunghiului
        if(b!=0)
            do /// Calculam CMMDC(a,b)
            {
                r=a%b;
                a=b;
                b=r;
            }
            while(r); /// in final a va fi cel mai mare divizor comun
        else
            if(a==0) /// pentru a prinde cazul particular in care ambele valori sunt 0
                a=1;
        /// (Y1==Y2&&abs(X2-X1)==1) <=> Segment orizontal de lungime 1
        /// (X1==X2&&abs(Y2-Y1)==1) <=> Segment vertical de lungime 1
        /// (X2==X1&&Y2==Y1&&abs(Y1-X1)==1) <=> Segment oblic de lungime 1
        if(a==1||(Y1==Y2&&abs(X2-X1)==1)||(X1==X2&&abs(Y2-Y1)==1)||(X2==X1&&Y2==Y1&&abs(Y1-X1)==1)) /// Daca e segment simplu,
            T[n++]=sqrt((X2-X1)*(X2-X1)+(Y2-Y1)*(Y2-Y1)); /// calculam distanta si o memoram
    }
    int mij,st,dr,Lmax=0;
    short int M_2[n]; /// M_2 este M fara ultimele 2 cifre
    char M2[n]; /// M2 este M cu ultimele doua cifre
    for(int i=0;i<n;++i)
    {
        st=1;
        dr=Lmax;
        while(st<=dr) /// Cautare binara
        {
            mij=(st+dr)/2;
            int mij_c=M_2[mij]*100+M2[mij]; /// Valoarea lui M[mij]
            if(T[mij_c]<=T[i])
                st=mij+1;
            else
                dr=mij-1;
        }
        if(st>Lmax)
            Lmax=st;
        M_2[st]=i/100;M2[st]=i%100; /// pun pe i in cei doi vectori
    }
    freopen ("masterpiece002.out","w",stdout);
    cout<<Lmax<<'\n';
    return 0;
}