masterpiece002

#include <cstdio>
#include <iostream>
#include <cmath>
#define Dmax 505050
using namespace std;

unsigned short readInt() /// Citirea numerelor intregi prin parsare
{
    bool minus=false;
    unsigned short raspuns=0;
    char c;
    while(true)
    {
        c=getchar();
        if(c==EOF)
            return 1001;
        if(c=='-')
        {
            minus=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(minus)
        return -raspuns;
    return raspuns;
}

int main()
{
    float T[Dmax];
    int n=0; /// n=nr de segmente simple
    unsigned short X1,Y1,X2,Y2,a,b,r;
    freopen("masterpiece002.in", "r",stdin);
    bool SF_FIS=false;
    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,M[n];
    for(int i=0;i<n;++i)
    {
        st=1;
        dr=Lmax;
        while(st<=dr) /// Cautare binara
        {
            mij=(st+dr)/2;
            if(T[M[mij]]<=T[i])
                st=mij+1;
            else
                dr=mij-1;
        }
        M[st]=i;
        if(st>Lmax)
            Lmax=st;
    }
    freopen ("masterpiece002.out","w",stdout);
    cout<<Lmax<<'\n';
    return 0;
}