算法 第四版 习题 答案1.2 .pdfVIP

算法第四版习题答案1.2

/*

*1.2.1编写一个Point2D的用例，从命令行接受一个整数N。在单位正方形内生成N个

随机点，然后计算两点之间的最近距离

*/

publicclasstestPoint2D{

publictestPoint2D(){

//TODOAuto-generatedconstructorstub

}

publicstaticvoiddrawbox(doublebw,doublebh)

{

StdDraw.setPenRadius(0.005);

StdDraw.setPenColor(StdDraw.RED);

Interval1Dxinterval=newInterval1D(0,bw);

Interval1Dyinterval=newInterval1D(0,bh);

Interval2Dbox=newInterval2D(xinterval,yinterval);

box.draw();

}

publicstaticPoint2D[]drawpoint(intN)

{

Point2D[]p=newPoint2D[N];

for(inti=0;iN;i++)

{

doublex=Math.random();

doubley=Math.random();

p[i]=newPoint2D(x,y);

p[i].draw();

}

returnp;

}

publicstaticdoublefindmindist(Point2D[]p)

{

Point2Dp1=p[0];

Point2Dp2=p[1];

doublemindist=p[0].distanceTo(p[1]);

StdDraw.setPenRadius(0.002);

StdDraw.setPenColor(StdDraw.RED);

intn=p.length;

for(inti=1;in-1;i++)

for(intj=i+1;jn;j++)

{

doubletemp=p[i].distanceTo(p[j]);

if(tempmindist)

{mindist=temp;

p1=p[i];

p2=p[j];

}

}

p1.drawTo(p2);

StdOut.print(mindist=+mindist+p1.toString()+p2.toString());

returnmindist;

}

publicstaticvoidmain(String[]args){

intN=StdIn.readInt();//读取画点的数量

//StdDraw.setXscale(0,1);

//StdDraw.setYscale(0,1);

drawbox(1,1);//画出一个单位大小的正方形

StdDraw.setPenRadius(0.01);

StdDraw.setPenColor(StdDraw.BLACK);

//drawpoint(N);//画出N个点

doublemin=findmindist(drawpoint(N));

}

}

/*

*编写一个Interval1D的用例，从命令行接受一个整数N。从标准输入中读取N个间隔

（每个间隔由一对double值定义）并打印出所有相交的间隔对

*/

publicclasstestInterval1D{

publictestInterval1D(){

//TODOAuto-generatedconstructorstub

}

publicstaticvoidmain(String[]args){

//TODOAuto-generatedmethodstub

intN=StdIn.readInt();

Interval1D[]interval=newInterval1D[N];

intT=N;

while(N0){

doublelo=N;

doublehi=N+N;

interval[T-N]=newInterval1D(lo,hi);

StdOut.println(interval[T-N].toString());

N--;

}

StdOut.println(OUT:);

for(inti=0;iT-1;i++)

for(