//package com.example.osm;

import java.io.*;
import java.nio.*;
import java.util.*;

class Point { 
	public int x, y; 

	public Point(int x, int y) {
		this.x = x;
		this.y = y;
	}
}

public class OSMLib {
    final static double E7 = 10000000.0;

 	static int getX(long xy) { return (int)((xy & 0xffffffff00000000L) >> 32); }
  	static int getY(long xy) { return (int) (xy & 0xffffffffL); }
//	static long makeXY(int x, int y) { return (((long)x) << 32) | (y & 0xffffffffL); }


    static String Wrap(String text) {
        if (text.startsWith("@")) {
            return text.substring(1);
        }
        final int maxWidth = 4;   // ４文字
        int text_length = text.length();
        if (text_length <= maxWidth) return text;
        StringBuilder result = new StringBuilder();
        for (int ix = 0; ix < text_length; ) {
            StringBuilder line = new StringBuilder();
            char prevChar = '\0';
            while (ix < text_length) {
                char currentChar = text.charAt(ix);
                char nextChar = ix+1 < text.length() ? text.charAt(ix+1) : '\0';
                if ((currentChar == ' ' || currentChar == '　') &&
                        (prevChar == '\0' || !isASCII(prevChar)) &&
                        (nextChar == '\0' || !isASCII(nextChar)) ) {
                    ix++;
                    continue;   // スペースを無視する
                }
                if (currentChar == '\n') {
                    ix++; break;
                } else if (currentChar != ' ') {
                    line.append(currentChar);
                }
                ix++;
                if ((ix >= text_length || line.length() >= maxWidth) &&
                        canLineBreak(currentChar, nextChar)) {
                    if (nextChar == '\n') ix++;
                    break;
                }
                prevChar = currentChar;
            }   // １文字ずつlineバッファに追加する
            if (result.length() > 0) result.append("\n");
            result.append(line);
        }
        return result.toString();
    }

    static boolean canLineBreak(char prevChar, char nextChar) {
        if (nextChar==' ' || nextChar=='　' || nextChar=='\0' || nextChar=='\n') {
            return true;
        }
        if (nextChar=='）' || nextChar==')' || nextChar=='」') {
            return false;
        }
        if (isASCII(prevChar) && isASCII(nextChar)) {
            return false;  // 幅１文字が連続している場合
        }
        return true;
    }

    static boolean isASCII(char c) {
        return (c <= 127);
    }



    static void readAllChars(String file, CharBuffer cb) throws IOException {
        File f = new File(file);
		try (DataInputStream dis = new DataInputStream(new FileInputStream(file))) {
        	while (true) {
            	char c = dis.readChar();
            	cb.put(c);
        	}
        } catch (EOFException e) {
            ; // ファイル読み込み完了
        } catch (Exception e) {
            e.printStackTrace();
        }

    }

    static int readAllChars(String file, char[] ca) throws IOException {
        File f = new File(file);
		int ix = 0;
		try (DataInputStream dis = new DataInputStream(new FileInputStream(file))) {
        	while (true) {
				ca[ix++] = dis.readChar();
        	}
        } catch (EOFException e) {
            ; // ファイル読み込み完了
        } catch (Exception e) {
            e.printStackTrace();
        }
		return ix;
    }

    static void writeAllChars(String file, char[] ca, int offset, int length) throws IOException {
        File f = new File(file);
		try (DataOutputStream dos = new DataOutputStream(new FileOutputStream(file))) {
        	for (int n = 0; n < length; n++) {
				dos.writeChar(ca[offset+n]);
        	}
        } catch (Exception e) {
            e.printStackTrace();
        }

    }





    static byte[] readAllBytes(String file) throws IOException {
        File f = new File(file);
        int file_length = (int) f.length();
        byte[] buffer = new byte[file_length];
        FileInputStream is = new FileInputStream(file);
        for (int offset = 0; offset < file_length; ) {
            int nbytes = is.read(buffer, offset, file_length - offset);
            offset += nbytes;
        }
        is.close();
        return buffer;
    }



    public static boolean PointInPolygon(Point p, Point[] poly) {
        boolean inside = false;
        Point p1, p2, oldPoint = poly[0];
        for (int i = 0; i < poly.length; i++) {
            Point newPoint = poly[i];
if (newPoint == null) {
	System.out.printf("i=%d, length=%d\n", i, poly.length);
}
            if (newPoint.x > oldPoint.x) { p1 = oldPoint; p2 = newPoint; }
            else { p1 = newPoint; p2 = oldPoint; }
            if ((p1.x < p.x) == (p.x <= p2.x) && 
                ((double)(p.y - p1.y)*(p2.x - p1.x)) < 
				((double)(p2.y - p1.y)*(p.x - p1.x))) {
                inside = !inside;
            }
            oldPoint = newPoint;
        }
        return inside;
    }

    private final static float EPSILON = 1E-7f;
    static Cell centroid;
    static float max_size;

    private static class Cell implements Comparator<Object> {
        public float X, Y, H, D, Max;

		public Cell() {}

        public Cell(float x, float y, float h, float[][][] polygon) {
            X = x;
            Y = y;
            H = h;
            D = PointToPolygonDist(X, Y, polygon);

            if (centroid != null) {
                double dx = X - centroid.X;
                double dy = Y - centroid.Y;
                double distance_centroid = Math.sqrt(dx * dx + dy * dy);
                if (D > 0 && distance_centroid < max_size) 
                    D = (float)(D * (1 - distance_centroid / max_size));
            }

            Max = D + H * (float)Math.sqrt(2);
        }

	    public int compare(Object obj1, Object obj2) {
        	Cell cell1 = (Cell)obj1; 
        	Cell cell2 = (Cell)obj2; 

    	    float num1 = cell1.Max;
        	float num2 = cell2.Max;
         
        	if(num1 > num2) {
            	return 1;
        	} else if(num1 < num2) {
            	return -1;
        	} else{
            	return 0;
        	}
    	}

    }

    //Signed distance from point to polygon outline (negative if point is outside)
    static float PointToPolygonDist(float x, float y, float[][][] polygon) {
           boolean inside = false;
           //float minDistSq = float.PositiveInfinity;
           float minDistSq = Float.MAX_VALUE;
           for (int k = 0; k < polygon.length; k++) {
              float[][] ring = polygon[k];
              for (int i = 0, len = ring.length, j = len - 1; i < len; j = i++) {
                 float[] a = ring[i];
                 float[] b = ring[j];
                 if ((a[1] > y != b[1] > y) && (x < (b[0] - a[0]) * (y - a[1]) / (b[1] - a[1]) + a[0]))
                    inside = !inside;
                 minDistSq = Math.min(minDistSq, GetSegDistSq(x, y, a, b));
              }
           }
           return ((inside ? 1 : -1) * (float)Math.sqrt(minDistSq));
        }


        //Get squared distance from a point to a segment
        private static float GetSegDistSq(float px, float py, float[] a, float[] b) {
           float x = a[0];
           float y = a[1];
           float dx = b[0] - x;
           float dy = b[1] - y;

           if (!FloatEquals(dx, 0) || !FloatEquals(dy, 0)) {
              float t = ((px - x) * dx + (py - y) * dy) / (dx * dx + dy * dy);
              if (t > 1) {
                 x = b[0];
                 y = b[1];
              } else if (t > 0) {
                 x += dx * t;
                 y += dy * t;
              }
           }
           dx = px - x;
           dy = py - y;
           return (dx * dx + dy * dy);
        }


    public static long getCenter(long[] poly, int length) {
        float[][][] polygon = new float[1][][];
        polygon[0] = new float[length][];
        for (int n = 0; n < length; n++) {
            polygon[0][n] = new float[2];
            polygon[0][n][0] = getX(poly[n])/10000000.0f;
            polygon[0][n][1] = getY(poly[n])/10000000.0f;
        }
		Cell centroid = getCentroidCell(polygon);
        float[] point = getCenter(polygon, centroid);
		int lon = (int)(point[0]*10000000);
		int lat = (int)(point[1]*10000000);
		return (((long)lon)<<32) | (lat & 0xffffffffL);
        //return ((((long)(point[0]*10000000))<<32) + (int)(point[1]*10000000));
    }



    public static float[] getCenter(float[][][] polygon, Cell centroid) {
       //Find the bounding box of the outer ring
       float minX = Float.MAX_VALUE, minY = Float.MAX_VALUE;
       float maxX = Float.MIN_VALUE, maxY = Float.MIN_VALUE;
       for (int i = 0; i < polygon[0].length; i++) {
          float[] p = polygon[0][i];
          if (p[0] < minX) minX = p[0];
          if (p[1] < minY) minY = p[1];
          if (p[0] > maxX) maxX = p[0];
          if (p[1] > maxY) maxY = p[1];
       }

       float width  = maxX - minX;
       float height = maxY - minY;
       float cellSize = Math.min(width, height);
       float h = cellSize / 2;

        max_size = Math.max(width, height);

//        float precision = cellSize * 3.0f / 100.0f; // 3%.  2021.11.30
        float precision = cellSize * 0.05f; // 5%.  2021.11.30

       //A priority queue of cells in order of their "potential" (max distance to polygon)
       Queue<Cell> cellQueue = new PriorityQueue<Cell>(4, new Cell());
       //Queue<Cell> cellQueue = new PriorityQueue<Cell>();

       if (FloatEquals(cellSize, 0))
          return new float[] { minX, minY };

       //Take centroid as the first best guess
       //centroid = new Cell(centro[0], centro[1], h, polygon);
       Cell bestCell = centroid;

       //Cover polygon with initial cells
       for (double x = minX; x < maxX; x += cellSize) {
          for (double y = minY; y < maxY; y += cellSize) {
             Cell cell = new Cell((float)(x + h), (float)(y + h), h, polygon);
             //cellQueue.enqueue(cell.Max, cell);
             cellQueue.add(cell);
          }
       }



       //Special case for rectangular polygons
       Cell bboxCell = new Cell(minX + width/2, minY + height/2, 0, polygon);
       if (bboxCell.D > bestCell.D)
           bestCell = bboxCell;

       int numProbes = cellQueue.size();

        while (cellQueue.size() > 0) {
          //Pick the most promising cell from the queue
           //Cell cell = cellQueue.Dequeue();
           Cell cell = cellQueue.poll();

           //Update the best cell if we found a better one
           if (cell.D > bestCell.D) {
               bestCell = cell;
           }

           //Do not drill down further if there's no chance of a better solution
           if (cell.Max - bestCell.D <= precision)
                continue;

              //Split the cell into four cells
              h = cell.H / 2;
              Cell cell1 = new Cell(cell.X - h, cell.Y - h, h, polygon);
              cellQueue.add(cell1);
              Cell cell2 = new Cell(cell.X + h, cell.Y - h, h, polygon);
              cellQueue.add(cell2);
              Cell cell3 = new Cell(cell.X - h, cell.Y + h, h, polygon);
              cellQueue.add(cell3);
              Cell cell4 = new Cell(cell.X + h, cell.Y + h, h, polygon);
              cellQueue.add(cell4);
              numProbes += 4;
         }

         return (new float[] { bestCell.X, bestCell.Y });
    }


        //Get polygon centroid
        private static Cell getCentroidCell(float[][][] polygon) {
           float area = 0, x = 0, y = 0;
           float[][] ring = polygon[0];

           for (int i = 0, len = ring.length, j = len - 1; i < len; j = i++) {
              float[] a = ring[i];
              float[] b = ring[j];
              float f = a[0] * b[1] - b[0] * a[1];
              x += (a[0] + b[0]) * f;
              y += (a[1] + b[1]) * f;
              area += f * 2;
           }
           if (FloatEquals(area, 0))
              return (new Cell(ring[0][0], ring[0][1], 0, polygon));
           return (new Cell(x/area, y/area, 0, polygon));
        }


        static boolean FloatEquals(float a, float b) {
           return (Math.abs(a - b) < EPSILON);
        }


    public static boolean PointInPolygon(long p, long[] poly) {
        boolean inside = false;
        long p1, p2, oldPoint = poly[poly.length-1];
        for (int i = 0; i < poly.length; i++) {
            long newPoint = poly[i];
            if (getX(newPoint) > getX(oldPoint)) { p1 = oldPoint; p2 = newPoint; }
            else { p1 = newPoint; p2 = oldPoint; }

            if ( ( (getX(p1) < getX(p)) == (getX(p) <= getX(p2)) ) && 
                ( (double)(getY(p)  - getY(p1)) * (getX(p2) - getX(p1)) < 
				  (double)(getY(p2) - getY(p1)) * (getX(p)  - getX(p1)) )  ) {
                inside = !inside;
            }
            oldPoint = newPoint;
        }
        return inside;
    }

/*
    public static boolean PointInPolygon(long p, long[] poly) {
        boolean inside = false;
        long p1, p2, oldPoint = poly[poly.length-1];
        for (int i = 0; i < poly.length; i++) {
            long newPoint = poly[i];
            if ((newPoint>>32) > (oldPoint>>32)) { p1 = oldPoint; p2 = newPoint; }
            else { p1 = newPoint; p2 = oldPoint; }
            if (((p1>>32) < (p>>32)) == ((p>>32) <= (p2>>32)) && 
                ((double)((int)p) - (int)p1)*((p2>>32) - (p1>>32)) < 
				((double)((int)p2) - (int)p1)*((p>>32) - (p1>>32))) {
                inside = !inside;
            }
            oldPoint = newPoint;
        }
        return inside;
    }
*/




    static double toRadian(double deg) {
        return deg*Math.PI/180.0;   // ラジアンに変換
    }
    static double Deg2Rad(double deg) {  return deg * Math.PI / 180.0; }   

/*
    static double GetDistance(long lnglat1, long lnglat2) {
        int lng1 = getX(lnglat1);
        int lat1 = getY(lnglat1);
        int lng2 = getX(lnglat2);
        int lat2 = getY(lnglat2);
        return GetDistance(lng1, lat1, lng2, lat2);
    }
*/
    static double GetDistance(int lng1, int lat1, int lng2, int lat2) {   
        double r = 6378137; // 地球の半径（m）
        double dlat1 = Deg2Rad(lat1/E7);
        double dlng1 = Deg2Rad(lng1/E7);
        double dlat2 = Deg2Rad(lat2/E7);
        double dlng2 = Deg2Rad(lng2/E7);

        double d1 = Math.sin(dlat1) * Math.sin(dlat2);
        double d2 = Math.cos(dlat1) * Math.cos(dlat2) * Math.cos(dlng2 - dlng1);
        double distance = r * Math.acos(d1 + d2);   // 距離（m）
        return distance;
    }   // haversine

    static double calcWayLength(long[] xys) {
        return calcWayLength(xys, 0, xys.length);
	}

    static double calcWayLength(long[] xys, int offset, int length) {
		double distance = 0;
		int lng1 = getX(xys[offset]);
		int lat1 = getY(xys[offset]);
        for (int n = 1; n < length; n++) {
            int lng2 = getX(xys[n+offset]);
			int lat2 = getY(xys[n+offset]);
			distance += GetDistance(lng1, lat1, lng2, lat2);
			lng1 = lng2;
			lat1 = lat2;
        }
        return distance;
	}


    public static double calcWayArea(long[] xys) {
        return calcWayArea(xys, 0, xys.length);
	}

    static double calcWayArea(long[] xys, int offset, int length) {
		if (length <= 2) return 0;
		int[] lonlats = new int[length*2];
        for (int n = 0; n < length; n++) {
            lonlats[n*2]   = getX(xys[n+offset]);
			lonlats[n*2+1] = getY(xys[n+offset]);
        }
        return calcWayArea(lonlats);
	}

    public static double calcWayArea(int[] lonlats) {
        double Radius = 6378137 + 100;      // 長半径 + 楕円高（仮）
        double[] xs = new double[lonlats.length/2];
        double[] ys = new double[lonlats.length/2];
        for (int n = 0; n < lonlats.length/2; n++) {
            xs[n] = lonlats[n*2]/10000000.0;
            ys[n] = lonlats[n*2+1]/10000000.0;
        }
        double wayarea = 0;
        var x1 = xs[xs.length-2];
        var y1 = ys[ys.length-2];
        for (int n = 0; n < xs.length-1; n++) {
            var x2 = xs[n];
            var y2 = ys[n];
            wayarea += toRadian(x2-x1)*(2+Math.sin(toRadian(y1))+Math.sin(toRadian(y2)));
            x1 = x2;
            y1 = y2;
        }
        return wayarea * Radius * Radius / 2.0;
    }   // 反時計回りが正、時計回りは負となる（逆では）


	// １度＝約100km ⇒ 1m＝約0.00001度
    public static double PerpendicularDistance(long p, long p1, long p2) {
		double E7 = 10000000.0;
		double px = getX(p) / E7;
		double py = getY(p) / E7;
		double p1x = getX(p1) / E7;
		double p1y = getY(p1) / E7;
		double p2x = getX(p2) / E7;
		double p2y = getY(p2) / E7;
//System.out.printf("px= %f py=%f\n", px, py);

        double dx = p2x - p1x;
        double dy = p2y - p1y;
        double d = Math.sqrt(dx*dx + dy*dy);
        return Math.abs(px*dy - py*dx + p2x*p1y - p2y*p1x)/d;
    }

    public static void SimplifySection(long[] pnts, int i, int j, double epsilon) {
        if ((i + 1) == j) return;
//if (true) return;
        double maxDistance = -1.0;
        int maxIndex = i;
        for (int k = i + 1; k < j; k++) {
            double distance = PerpendicularDistance(pnts[k], pnts[i], pnts[j]);
//System.out.printf("d= %f\n", distance);
            if (distance > maxDistance) {
                maxDistance = distance;
                maxIndex = k;
            }
        }
        if (maxDistance <= epsilon) {
            for (int k = i + 1; k < j; k++) {
                pnts[k] = Long.MIN_VALUE;   // 間引く
//System.out.printf("simplify: %X\n", pnts[k]);
            }
        } else {
            SimplifySection(pnts, i, maxIndex, epsilon);
            SimplifySection(pnts, maxIndex, j, epsilon);
        }
    }

/**
	// １度＝約100km ⇒ 1m＝約0.00001度
    public static double PerpendicularDistance(int x, int y, int x1, int y1, int x2, int y2) {
		double E7 = 10000000.0;
		double px = x / E7;
		double py = y / E7;
		double p1x = x1 / E7;
		double p1y = y1 / E7;
		double p2x = x2 / E7;
		double p2y = y2 / E7;
//System.out.printf("px= %f py=%f\n", px, py);

        double dx = p2x - p1x;
        double dy = p2y - p1y;
        double d = Math.sqrt(dx*dx + dy*dy);
        return Math.abs(px*dy - py*dx + p2x*p1y - p2y*p1x)/d;
    }

    public static void SimplifySection(int[] pnts, int i, int j, double epsilon) {
        if ((i + 1) == j) return;
//if (true) return;
        double maxDistance = -1.0;
        int maxIndex = i;
        for (int k = i + 1; k < j; k++) {
            double distance = PerpendicularDistance(
						pnts[2*k], pnts[2*k+1], pnts[2*i], pnts[2*i+1], pnts[2*j], pnts[2*j+1]);
//System.out.printf("d= %f\n", distance);
            if (distance > maxDistance) {
                maxDistance = distance;
                maxIndex = k;
            }
        }
        if (maxDistance <= epsilon) {
            for (int k = i + 1; k < j; k++) {
                pnts[2*k]   = Integer.MIN_VALUE;   // 間引く
                pnts[2*k+1] = Integer.MIN_VALUE;   // 間引く
//System.out.printf("simplify: %X\n", pnts[k]);
            }
        } else {
            SimplifySection(pnts, i, maxIndex, epsilon);
            SimplifySection(pnts, maxIndex, j, epsilon);
        }
    }
**/

}