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.
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.
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;
}
}
