task07のヒント1 • findUpperTangent – 左側の凸多角形で、反時計回りに次の頂点をだすには？ int i1 = (i + 1) % left.length; – 右側の凸多角形で、時計回りに次の頂点をだすには？ – データは反時計回りに入っているから、1個前のデータを取り出せばよい． int j1 = (j – + )% データ構造とアルゴリズム実習２ Iguchi findLowerTangent • findUpperTangentを見本にすればよい • 線分は右から左向きに引くデータ構造とアルゴリズム実習２ Iguchi public static int[] findLowerTangent(Point left[], Point right[]) { // 右の多角形の最左の頂点に注目し、その番号を i とする。 int i = leftmostPointIndex(right); // 左の多角形の最右の頂点に注目し、その番号を j とする。 int j = rightmostPointIndex(left); while (true) { // i1 によって、右の凸多角形において i番の頂点の反時計回りで次の点の // 番号を表す。 int nRight = right.length; // 左側の凸多角形の頂点数 int i1 = (i + 1) % ; // j1 によって、右の凸多角形において j番の頂点の時計回りで次の点の // 番号を表す。 int nLeft = left.length; // 右側の凸多角形の頂点数 int j1 = (j ) % nLeft; // right[i] と left[j] を結ぶ直線Lと left[j1] および // right[i1] の位置関係を調べる。 // どちらかの点が直線の下方にあれば、点を移動する。 // なけらばwhile 分を抜ける。 if (right[i1].isLeft(right[i], left[j])) { // right[i1] は L の上方にある i = i1; } else if ( ){ // left[j1] は L の上方にある j = j1; } else break; } int t[] = new int[2]; // 接点の番号を配列に入れて返す。 t[0] = j; t[1] = i; return t; } データ構造とアルゴリズム実習２ Iguchi leftmostPointIndex(Point p[]) /* * 与えられたPoint 配列中で、 x 座標が最小の点の、配列中での番号（インデックス） * を返す。 */ private static int leftmostPointIndex(Point p[]) { int k = 0; /*** k が答えになるように正しいコードで埋めてください。***/ int minX = p[k].getX(); for(int i = 1; i < p.length; i++){ if(p[i].getX() < minX){ k = i; } } return k; } rightmostPointIndexも同様に書けばよいデータ構造とアルゴリズム実習２ Iguchi