Friday 31 October 2014

PROJECT EULER SOLUTION # 165

Projecteuler Problem # 165:
A segment is uniquely defined by its two endpoints.
By considering two line segments in plane geometry there are three possibilities:
the segments have zero points, one point, or infinitely many points in common.
Moreover when two segments have exactly one point in common it might be the case that that common point is an endpoint of either one of the segments or of both. If a common point of two segments is not an endpoint of either of the segments it is an interior point of both segments.
We will call a common point T of two segments L1 and L2 a true intersection point of L1 and L2 if T is the only common point of L1and L2 and T is an interior point of both segments.
Consider the three segments L1, L2, and L3:
L1: (27, 44) to (12, 32)

L2: (46, 53) to (17, 62)

L3: (46, 70) to (22, 40)
It can be verified that line segments L2 and L3 have a true intersection point. We note that as the one of the end points of L3: (22,40) lies on L1 this is not considered to be a true point of intersection. L1 and L2 have no common point. So among the three line segments, we find one true intersection point.
Now let us do the same for 5000 line segments. To this end, we generate 20000 numbers using the so-called "Blum Blum Shub" pseudo-random number generator.
s0 = 290797

sn+1 = sn×sn (modulo 50515093)

tn = sn (modulo 500)
To create each line segment, we use four consecutive numbers tn. That is, the first line segment is given by:
(t1, t2) to (t3, t4)
The first four numbers computed according to the above generator should be: 27, 144, 12 and 232. The first segment would thus be (27,144) to (12,232).
How many distinct true intersection points are found among the 5000 line segments?
The following is the solution to the above mentioned problem in java.
But I didn’t reach at this solution in a single go; rather it was a step by step procedure.
First I would like to present the correct solution and then I would like to give you all the mistakes that I committed in the path while devising this solution.
/************************************************************/
Pe165.java
package pe165efficient;

public class pe165
{
      public static int heapLength; // for heap sort
     
      static Fraction x[]; // Array for storing the x coordinate of intersection points
      static Fraction y[]; // Array for storing the y coordinate of intersection points
      static int size=2868997; // this is the total number of intersection points, some of these points may be repeated.
      static int indexOfArray=0; // index of the intersection point array.
     
      /****************/
      /*
       * for heap sort
       */
      public static int getParentIndex(int n)
      {
            return (n/2);
      }
      public static int getLeftChildIndex(int n)
      {
            return n*2;
      }
      public static int getRightChildIndex(int n)
      {
            return n*2+1;
      }
     
      public static void maxHeapify(Fraction[]x,Fraction[]y,int i)
      {
            int l=getLeftChildIndex(i+1)-1; // our array is zero indexed array...
            int r=getRightChildIndex(i+1)-1;
            int largest;
            Fraction tmp;
            if(l<=heapLength-1 && x[l].n>x[i].n)
                  largest=l;
            else
                  largest=i;
                 
            if(r<=heapLength-1 && x[r].n>x[largest].n)
                  largest=r;
           
            // exchange x[i] and x[largest]
            if(largest!=i)
            {
                  tmp=x[i];
                  x[i]=x[largest];
                  x[largest]=tmp;
                 
                  tmp=y[i];
                  y[i]=y[largest];
                  y[largest]=tmp;
                 
                  maxHeapify(x,y,largest);
            }
      }
     
      public static void buildMaxHeap(Fraction[]x,Fraction[]y)
      {
            for(int i=getParentIndex(indexOfArray)-1;i>=0;i--)
                  maxHeapify(x,y,i);
      }
     
      public static void heapSort(Fraction[]x,Fraction[]y)
      {
            buildMaxHeap(x,y);
            Fraction tmp;
            for(int i=indexOfArray-1;i>=1;i--)
            {
                  tmp=x[0];
                  x[0]=x[i];
                  x[i]=tmp;
                 
                  tmp=y[0];
                  y[0]=y[i];
                  y[i]=tmp;
                 
                  heapLength--;
                  maxHeapify(x,y,0);
            }
      }
      /*
       * heap sort code finishes here
       */
      /*******************/
      public static void calculateS(long t[])
      {
          int i;
          long s[]=new long[20001];
          s[0]=290797;
          for(i=1;i<=20000;i++)
          {
              s[i]=(s[i-1]*s[i-1])%50515093;
              t[i]=s[i]%500;
          }
      }

      public static long direction(long xi,long yi,long xj,long yj,long xk,long yk)
      {
            long ax,ay,bx,by;
          ax=xk-xi;
          ay=yk-yi;
          bx=xj-xi;
          by=yj-yi;

          return (ax*by-bx*ay);
      }

      public static void calculateIntersectionPoint(long a,long b,long c,long d,long e,long f,long g,long h)
      {
            /*
             * this method calculate the intersection point and stores it in x and y array as Fraction
             */
          long xNumerator,xDenominator,yNumerator,yDenominator;
          xNumerator=-a*d*e + a*d*g + a*e*h - a*f*g + b*c*e - b*c*g - c*e*h + c*f*g;
          xDenominator=-a*f + a*h + b*e - b*g + c*f - c*h - d*e + d*g;
         
          yNumerator=a*d*f - a*d*h - b*c*f + b*c*h - b*e*h + b*f*g + d*e*h - d*f*g;
          yDenominator=a*f - a*h - b*e + b*g - c*f + c*h + d*e - d*g;
         
          Fraction xFraction=new Fraction(xNumerator,xDenominator);
          Fraction yFraction=new Fraction(yNumerator,yDenominator);
         
          x[indexOfArray]=xFraction;
          y[indexOfArray]=yFraction;
         
          indexOfArray++;
      }

      public static void segmentsIntersect(long x1,long y1,long x2,long y2,long x3,long y3,long x4,long y4)
      {
            long d1,d2,d3,d4;
          d1=direction(x3,y3,x4,y4,x1,y1);
          d2=direction(x3,y3,x4,y4,x2,y2);
          d3=direction(x1,y1,x2,y2,x3,y3);
          d4=direction(x1,y1,x2,y2,x4,y4);
          if(((d1>0&&d2<0) || (d1<0&&d2>0)) && ((d3>0&&d4<0) || (d3<0&&d4>0)))
              // means segments have a true intersection point.
              calculateIntersectionPoint(x1,y1,x2,y2,x3,y3,x4,y4); // this function calculates the true intersection point of the the two given segemnts.
      }

      public static void main(String args[])
      {
            System.out.println("Started");
            long startTime=System.currentTimeMillis();
            int i,j;
          long t[]=new long[20001];
         
          x=new Fraction[size];
          y=new Fraction[size];
         
          calculateS(t);
          for(i=0;i<5000;i++)
            for(j=i+1;j<5000;j++)
                  segmentsIntersect(t[i*4+1],t[i*4+2],t[i*4+3],t[i*4+4],t[j*4+1],t[j*4+2],t[j*4+3],t[j*4+4]);
         
          heapLength=indexOfArray;
            heapSort(x,y);
            int answer=indexOfArray;
         
          boolean booleanArray[]=new boolean[indexOfArray];
           
          for(i=0;i<indexOfArray;i=j)
          {
            for(j=i+1;j<indexOfArray && x[i].n==x[j].n;j++);
            for(int p=i;p<j;p++)
                  if(booleanArray[i]==false)
                        for(int q=p+1;q<j;q++)
                              if(x[p].equals(x[q]) && y[p].equals(y[q]) && booleanArray[q]==false)
                              {
                                    booleanArray[q]=true;
                                    answer--;
                              }
          }
            System.out.println("Answer = "+answer);
            System.out.println("Execution time = "+((System.currentTimeMillis()-startTime)/1000.0));
      }
}

Fraction.java
package pe165efficient;
public class Fraction
{
      public long n,d;
      double value;
      public Fraction(long n,long d)
      {
            this.n=n;
            this.d=d;
            simplifyFraction();
      }
     
      public void simplifyFraction()
      {
            long h=hcf(Math.abs(n),Math.abs(d));
            n/=h;
            d/=h;
            if(d<0)
            {
                  d=-d;
                  n=-n;
            }
            value=(double)n/(double)d;
      }
     
      public long hcf(long a,long b)
      {
            if(b==0)
                  return a;
            return hcf(b,a%b);
      }
     
      public boolean equals(Fraction f)
      {
            if((this.n==f.n && f.n==0) || (this.n==f.n && this.d==f.d))
                  return true;
            return false;
      }
}

/****************************************************************/
You all might be wondering that from where the number 2868997 came. You will get your answer soon in the following lines.
Now as the solution is ended I would like to tell you all how it all started, what were the mistakes that I committed and what were my learnings.
I started with a very simple C program. I would like to give that program here:

//first trial

#include<stdio.h>

int calculateS(int*t)
{
       int i,s[20001];
       s[0]=290797;
       t[0]=s[0]%500;
       for(i=1;i<=20000;i++)
       {
           s[i]=((((long long int)(s[i-1])*s[i-1])%50515093));
           t[i]=s[i]%500;
       }
}

int direction(int xi,int yi,int xj,int yj,int xk,int yk)
{
       int ax,ay,bx,by;
       ax=xk-xi;
       ay=yk-yi;
       bx=xj-xi;
       by=yj-yi;
     
       return (ax*by-bx*ay);
}

int segmentsIntersect(int x1,int y1,int x2,int y2,int x3,int y3,int x4,int y4)
{
       int d1,d2,d3,d4;
       d1=direction(x3,y3,x4,y4,x1,y1);
       d2=direction(x3,y3,x4,y4,x2,y2);
       d3=direction(x1,y1,x2,y2,x3,y3);
       d4=direction(x1,y1,x2,y2,x4,y4);
       if(((d1>0&&d2<0) || (d1<0&&d2>0)) && ((d3>0&&d4<0) || (d3<0&&d4>0)))
           return 1;
       return 0;
}

int main()
{
       int t[20001],i,j,answer=0;
       calculateS(t);
       for(i=0;i<5000;i++)
           for(j=i+1;j<5000;j++)
               if(segmentsIntersect(t[i*4+1],t[i*4+2],t[i*4+3],t[i*4+4],t[j*4+1],t[j*4+2],t[j*4+3],t[j*4+4]))
                   answer++;
       printf("answer = %d\n",answer);
       return 0;
}

No doubt, this above program gave me a wrong answer, but then also I got to know a lot many things that helped me at a later point of time while designing the correct solution. The most important thing that I got to know from this wrong answer was that, there are in total 2868997 numbers of total intersections (although not unique). Now I got to know where I got the number 2868997. And this was the only mistake that I had done; I didn’t get through the above program total number of unique intersections rather I got total number of intersection without the “unique” clause. Also I would like to quote the execution time of this program that is as low as 0.894 sec.
The above program is very easy to understand and I would suggest you all to read the chapter related to Computational Geometry in Cormen specially the topic “Determining whether tow line segments intersect or not”. This will definitely be helpful to you all.


Now to implement the unique clause I designed the following C program, which inserts a new intersection point only after searching the previously inserted points. If the new point is found in previously inserted points than I don’t insert it into the solution, otherwise it is inserted in the solution.

#include<stdio.h>
#include<stdlib.h>
double x[2868997];
double y[2868997];
int size=2868997;
int calculateS(int*t)
{
    int i,s[20001];
    s[0]=290797;
    t[0]=s[0]%500;
    for(i=1;i<=20000;i++)
    {
        s[i]=((((long long int)(s[i-1])*s[i-1])%50515093));
        t[i]=s[i]%500;
    }
}

int direction(int xi,int yi,int xj,int yj,int xk,int yk)
{
    int ax,ay,bx,by;
    ax=xk-xi;
    ay=yk-yi;
    bx=xj-xi;
    by=yj-yi;

    return (ax*by-bx*ay);
}

int search(double *a,double n)
{
    int i;
    for(i=0;i<size;i++)
    {
        if(a[i]==n)
            return i; // if element found then return index.
    }
    return -1; // if element not found then return -1
}

void calculateIntersectionPoint(int a,int b,int c,int d,int e,int f,int g,int h)
{
    int searchx,searchy;
    double xcoordinate,ycoordinate;
    xcoordinate=((double)(f*g+a*d-e*h-b*c)*(c-a)*(g-e))/((d-b)*(g-e)-(h-f)*(c-a));
    ycoordinate=((double)(f*g+a*d-e*h-b*c)*(c-a)*(g-e))/((d-b)*(g-e)-(h-f))*((d-b))+b*c-a*d;
    searchx=search(x,xcoordinate);
    searchy=search(y,ycoordinate);
    if(searchx!=-1 && searchy!=-1)
    {
        // means element is found
    }
    else
    {
        /*
        size++;
        x=(double*)realloc(x,size*sizeof(double));
        y=(double*)realloc(y,size*sizeof(double));
        */
        x[searchx]=xcoordinate;
        y[searchy]=ycoordinate;
    }
}

int segmentsIntersect(int x1,int y1,int x2,int y2,int x3,int y3,int x4,int y4)
{
    int d1,d2,d3,d4;
    d1=direction(x3,y3,x4,y4,x1,y1);
    d2=direction(x3,y3,x4,y4,x2,y2);
    d3=direction(x1,y1,x2,y2,x3,y3);
    d4=direction(x1,y1,x2,y2,x4,y4);
    if(((d1>0&&d2<0) || (d1<0&&d2>0)) && ((d3>0&&d4<0) || (d3<0&&d4>0)))
    {
        calculateIntersectionPoint(x1,y1,x2,y2,x3,y3,x4,y4);
        return 1;
    }
    return 0;
}

int main()
{
    int t[20001],i,j,answer=0;
    calculateS(t);

    for(i=0;i<5000;i++)
    {
        printf("%d size = %d\n",i,size);
        for(j=i+1;j<5000;j++)
        {
            segmentsIntersect(t[i*4+1],t[i*4+2],t[i*4+3],t[i*4+4],t[j*4+1],t[j*4+2],t[j*4+3],t[j*4+4]);
        }
    }
    return 0;
}

But the above solution does not satisfy the practical time limits and will take time as if some combinatorial explosion occurred. I was really disheartened with the above approach, as now I just have to eliminate all the duplicate entries from the solution.

Then I decided to opt for java, and I converted my previously running code in c and then continue the marathon.
So this was my first code in java

package pe165;

public class pe165
{

      static float x[];
      static float y[];
      int size=2868997;
      static int indexOfArray=0;

      public static void calculateS(int t[])
      {
          int i;
          int s[]=new int[20001];
          s[0]=290797;
          t[0]=s[0]%500;
          for(i=1;i<=20000;i++)
          {
              s[i]=(int)((((long)(s[i-1])*s[i-1])%50515093));
              t[i]=s[i]%500;
          }
      }

      public static int direction(int xi,int yi,int xj,int yj,int xk,int yk)
      {
          int ax,ay,bx,by;
          ax=xk-xi;
          ay=yk-yi;
          bx=xj-xi;
          by=yj-yi;

          return (ax*by-bx*ay);
      }

      public static void calculateIntersectionPoint(int a,int b,int c,int d,int e,int f,int g,int h)
      {
          float xcoordinate,ycoordinate;
          xcoordinate=((float)(f*g+a*d-e*h-b*c)*(c-a)*(g-e))/((d-b)*(g-e)-(h-f)*(c-a));
          ycoordinate=((float)(f*g+a*d-e*h-b*c)*(c-a)*(g-e))/((d-b)*(g-e)-(h-f))*((d-b))+b*c-a*d;

          x[indexOfArray]=xcoordinate;
          y[indexOfArray]=ycoordinate;
          indexOfArray++;
      }

      public static int segmentsIntersect(int x1,int y1,int x2,int y2,int x3,int y3,int x4,int y4)
      {
          int d1,d2,d3,d4;
          d1=direction(x3,y3,x4,y4,x1,y1);
          d2=direction(x3,y3,x4,y4,x2,y2);
          d3=direction(x1,y1,x2,y2,x3,y3);
          d4=direction(x1,y1,x2,y2,x4,y4);
          if(((d1>0&&d2<0) || (d1<0&&d2>0)) && ((d3>0&&d4<0) || (d3<0&&d4>0)))
          {
              // means segments have a true intersection point.
              calculateIntersectionPoint(x1,y1,x2,y2,x3,y3,x4,y4);
              return 1;
          }
          return 0;
      }

      public static void main(String args[])
      {
          int i,j;
          int t[]=new int[20001];
          x=new float[2868997];
          y=new float[2868997];

          calculateS(t);

          for(i=0;i<5000;i++)
          {
            System.out.println(i);
              for(j=i+1;j<5000;j++)
                  segmentsIntersect(t[i*4+1],t[i*4+2],t[i*4+3],t[i*4+4],t[j*4+1],t[j*4+2],t[j*4+3],t[j*4+4]);
          }

      }

}

It did nothing new, but it was the main base of my successful solution.
Then after 3-4 more intermediate programs in java I reached to the final program and got a correct answer.
I would also like to mention the mistakes that I committed. The silliest mistake was in heap sort, in the heap sort I was supposed to swap two objects, one related to the x coordinate and the other related to the y coordinate, but I missed swapping the y object among one of the swapping.
My basic pushing force that motivated me towards sorting was that after sorting I can easily eliminate the duplicates, and sorting (especially heap sort) would cost me not more than O(n lg(n)). And this was the most beautiful thing about this algorithm.
Another important thing that I liked was the designing of the Fraction class. And overriding the previously build equals function in java library. Although this specific definition would suffice but I thought it is good to implement the Fraction class in fully functional form.
The following is the correct program for the solution to the problem number 165 of projecteuler, but is not as efficient as the first one. I have completely eliminated the Segment class for simplicity and efficiency. Also I have eliminated the redundant comments and code in the first program.
The following is the inefficient version of the first program.
Solution 165:
pe165.java

package pe165;

public class pe165
{
     
      public static int heapLength;
     
      static Fraction x[];
      static Fraction y[];
      static int size=2868997;
      static int indexOfArray=0;
     
     
      /****************/
      /*
       * for heap sort
       */

      public static int getParentIndex(int n)
      {
            return (n/2);
      }
      public static int getLeftChildIndex(int n)
      {
            return n*2;
      }
      public static int getRightChildIndex(int n)
      {
            return n*2+1;
      }
     
      public static void maxHeapify(Fraction[]x,Fraction[]y,int i)
      {
            int l=getLeftChildIndex(i+1)-1; // our array is zero indexed array...
            int r=getRightChildIndex(i+1)-1;
            int largest;
            Fraction tmp;
            if(l<=heapLength-1 && x[l].n>x[i].n)
                  largest=l;
            else
                  largest=i;
                 
            if(r<=heapLength-1 && x[r].n>x[largest].n)
                  largest=r;
           
            // exchange x[i] and x[largest]
            if(largest!=i)
            {
                  tmp=x[i];
                  x[i]=x[largest];
                  x[largest]=tmp;
                 
                  tmp=y[i];
                  y[i]=y[largest];
                  y[largest]=tmp;
                 
                  maxHeapify(x,y,largest);
            }
      }
     
      public static void buildMaxHeap(Fraction[]x,Fraction[]y)
      {
            for(int i=getParentIndex(indexOfArray)-1;i>=0;i--)
                  maxHeapify(x,y,i);
      }
     
      public static void heapSort(Fraction[]x,Fraction[]y)
      {
            buildMaxHeap(x,y);
            Fraction tmp;
            for(int i=indexOfArray-1;i>=1;i--)
            {
                  tmp=x[0];
                  x[0]=x[i];
                  x[i]=tmp;
                 
                  tmp=y[0];
                  y[0]=y[i];
                  y[i]=tmp;
                 
                  heapLength--;
                  maxHeapify(x,y,0);
            }
      }
      /*
       * heap sort code finishes here
       */
      /*******************/
      public static void calculateS(long t[])
      {
          int i;
          long s[]=new long[20001];
          s[0]=290797;
          t[0]=s[0]%500;
          for(i=1;i<=20000;i++)
          {
              s[i]=(s[i-1]*s[i-1])%50515093;
              t[i]=s[i]%500;
              //System.out.println("t["+i+"] = "+t[i]);
          }
      }

      public static long direction(long xi,long yi,long xj,long yj,long xk,long yk)
      {
            long ax,ay,bx,by;
          ax=xk-xi;
          ay=yk-yi;
          bx=xj-xi;
          by=yj-yi;

          return (ax*by-bx*ay);
      }

      public static void calculateIntersectionPoint(long a,long b,long c,long d,long e,long f,long g,long h)
      {
            /*
             * this method calculate the intersection point and stores it in x and y array as Fraction
             */
          long xNumerator,xDenominator,yNumerator,yDenominator;
          /*
          xNumerator=(f*g-e*h)*(c-a)+(a*d-b*c)*(g-e);
          xDenominator=(d-b)*(g-e)-(h-f)*(c-a);
         
          if(c!=a)
            {
            yNumerator=xNumerator*(d-b)+(b*c-a*d)*xDenominator;
            yDenominator=xDenominator*(c-a);
            }
          else
          {
            yNumerator=xNumerator*(h-f)+(f*g-e*h)*xDenominator;
            yDenominator=xDenominator*(g-e);
          }
         
          if(xDenominator==0 || yDenominator==0)
            return;
         
          */
          xNumerator=-a*d*e + a*d*g + a*e*h - a*f*g + b*c*e - b*c*g - c*e*h + c*f*g;
          xDenominator=-a*f + a*h + b*e - b*g + c*f - c*h - d*e + d*g;
         
          yNumerator=a*d*f - a*d*h - b*c*f + b*c*h - b*e*h + b*f*g + d*e*h - d*f*g;
          yDenominator=a*f - a*h - b*e + b*g - c*f + c*h + d*e - d*g;
         
         
          Fraction xFraction=new Fraction(xNumerator,xDenominator);
          Fraction yFraction=new Fraction(yNumerator,yDenominator);
         
          /*
          the following is the check for the true intersection point.
          if((xFraction.d==1&&yFraction.d==1) && ((xFraction.n==a&&yFraction.n==b) || (xFraction.n==c&&yFraction.n==d) || (xFraction.n==e&&yFraction.n==f) || (xFraction.n==g&&yFraction.n==h)))
            return ;
          */
         
          x[indexOfArray]=xFraction;
          y[indexOfArray]=yFraction;
         
          //System.out.println(a+","+b+"#"+c+","+d+"#"+e+","+f+"#"+g+","+h+"\t"+"xn="+x[indexOfArray].n+" xd="+x[indexOfArray].d+" yn="+y[indexOfArray].n+" yd="+y[indexOfArray].d);
         
          indexOfArray++;
      }

      public static int segmentsIntersect(long x1,long y1,long x2,long y2,long x3,long y3,long x4,long y4)
      {
            long d1,d2,d3,d4;
          d1=direction(x3,y3,x4,y4,x1,y1);
          d2=direction(x3,y3,x4,y4,x2,y2);
          d3=direction(x1,y1,x2,y2,x3,y3);
          d4=direction(x1,y1,x2,y2,x4,y4);
          if(((d1>0&&d2<0) || (d1<0&&d2>0)) && ((d3>0&&d4<0) || (d3<0&&d4>0)))
          {
              // means segments have a true intersection point.
              calculateIntersectionPoint(x1,y1,x2,y2,x3,y3,x4,y4); // this function calculates the true intersection point of the the two given segemnts.
              return 1;
          }
          return 0;
      }

      public static void main(String args[])
      {
            System.out.println("Started");
          int i,j;
          long t[]=new long[20001];
         
          x=new Fraction[size];
          y=new Fraction[size];
         
          calculateS(t);
          Segment segmentArray[]=new Segment[5000];
          for(i=0;i<5000;i++)
          {
            segmentArray[i]=new Segment(t[i*4+1],t[i*4+2],t[i*4+3],t[i*4+4]);
          }
         
          for(i=0;i<5000;i++)
          {
            //System.out.println(i);
              for(j=i+1;j<5000;j++)
                  segmentsIntersect(segmentArray[i].a,segmentArray[i].b,segmentArray[i].c,segmentArray[i].d,segmentArray[j].a,segmentArray[j].b,segmentArray[j].c,segmentArray[j].d);
          }
          System.out.println("this is a check : "+indexOfArray);
          heapLength=indexOfArray;
            heapSort(x,y);
            /*
            for(i=0;i<500;i++)
                  System.out.println(x[i]+","+y[i]);
            */
            System.out.println("sorted");
          int answer=indexOfArray;
         
          /*
          for(i=0;i<50;i++)
            System.out.println("for x=>n = "+x[i].n+"\t d = "+x[i].d+"\t for y=>n = "+y[i].n+"\t d = "+y[i].d);
            */
          System.out.println("you are now entering to eliminate the duplicate elements...");
         
            boolean booleanArray[]=new boolean[indexOfArray];
           
            for(i=0;i<indexOfArray;i++)
                  booleanArray[i]=false;
            /*
            System.out.println("The long process has started...");
            for(i=0;i<indexOfArray;i++)
            {
                  System.out.println(i);
                  if(booleanArray[i]==false)
                  {
                        for(j=i+1;j<indexOfArray;j++)
                        {
                              if(x[i].equals(x[j]) && y[i].equals(y[j]))
                              {
                                    System.out.println("Found an enemy");
                                    booleanArray[i]=booleanArray[j]=true;
                                    answer--;
                              }
                        }
                  }
            }
            */
            for(i=0;i<indexOfArray;)
          {
            for(j=i+1;j<indexOfArray && x[i].n==x[j].n;j++);
            /*
            if(j==i+1)
            {
                  i++;
                  continue;
            }
            */
            for(int p=i;p<j;p++)
            {
                  if(booleanArray[i]==false)
                  {
                        for(int q=p+1;q<j;q++)
                        {
                              if(x[p].equals(x[q]) && y[p].equals(y[q]) && booleanArray[q]==false)
                              //if(x[p].value==x[q].value && y[p].value==y[q].value)
                              {
                                    booleanArray[q]=true;
                                   
                                    System.out.println("You got an enemy");
                                   
                                    answer--;
                              }
                        }
                  }
            }
            i=j;
          }
         
            System.out.println(answer);
      }
}

Segment.java
package pe165;

public class Segment
{
      public long a,b,c,d;
      public Segment(long a,long b,long c,long d)
      {
            this.a=a;
            this.b=b;
            this.c=c;
            this.d=d;
      }
}

Fraction.java
package pe165;

public class Fraction
{
      public long n,d;
      double value;
      public Fraction(long n,long d)
      {
            this.n=n;
            this.d=d;
            simplifyFraction();
      }
     
      public void simplifyFraction()
      {
            long h=hcf(Math.abs(n),Math.abs(d));
            n/=h;
            d/=h;
            if(d<0)
            {
                  d=-d;
                  n=-n;
            }
            value=(double)n/(double)d;
      }
     
      public long hcf(long a,long b)
      {
            if(b==0)
                  return a;
            return hcf(b,a%b);
      }
     
      public boolean equals(Fraction f)
      {
            if((this.n==f.n && f.n==0) || (this.n==f.n && this.d==f.d))
                  return true;
            return false;
      }
}