masterplace002_100PUNCTE

#include <cstdio>
#include <iostream>
#include <cmath>
#define Dmax 505050
using namespace std;
unsigned short int TI[Dmax]; /// TI=Partea intreaga
unsigned char TF[Dmax]; /// iar TF=partea fractionara

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
        float x;
        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,
        {
            x=sqrt((X2-X1)*(X2-X1)+(Y2-Y1)*(Y2-Y1)); /// calculam distanta
            TI[n]=(int)x;TF[n++]=100*(x-(int)x); /// si o memoram in cei doi vectori
        }
    }
    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(TI[mij_c]<=TI[i])
            {
                if(TI[mij_c]<TI[i]) /// Intregii sunt in relatia <
                    st=mij+1;
                else /// Intregii sunt egali
                    if(TF[mij_c]<=TF[i]) /// Fractiile sunt mai mici sau egale
                        st=mij+1;
                    else /// Fractiile sunt mai mari
                        dr=mij-1;
            }
            else /// Intregii sunt mai mari
                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;
}