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

// 座標は XY平面座標
public class Polygon {
    static double B30 = 1024*1024*1024;   // (2 の 30乗)

    int length;         // 実際のノード数
    int size;           // 配列のサイズ
    int[] xs;           // 
    int[] ys;           // 
    int xmin, ymin, xmax, ymax;
    int iXmax, iYmax;   // xs[iXmax] == xmax, ys[iYmax] == ymax
    boolean fSplit = false; // オリジナルpolygonでないとき true

    public Polygon(int size) {
        this.size = size;
        xs = new int[size];
        ys = new int[size];
        length = 0;
    }

    public Polygon(int[] xs, int[] ys) {
        length = size = Math.min(xs.length, ys.length);
        this.xs = new int[size];
        this.ys = new int[size];
        System.arraycopy(xs, 0, this.xs, 0, length);
        System.arraycopy(ys, 0, this.ys, 0, length);
        setMinMax();
    }   // 入力の xs.length と ys.length が異なる場合、小さい方をとる。

    int next(int i) { return (i + 1) % length; }
        
    // 境界ボックスと X座標、Y座標が最大となるインデックスを求める
    void setMinMax() {
        xmin = xmax = xs[0];
        ymin = ymax = ys[0];
        iXmax = iYmax = 0;
        for (int i = 1; i < length; i++) {
            if (xs[i] < xmin) { xmin = xs[i]; }
            if (xs[i] > xmax) { xmax = xs[i]; iXmax = i; }
            if (ys[i] < ymin) { ymin = ys[i]; }
            if (ys[i] > ymax) { ymax = ys[i]; iYmax = i; }
        }
    }

    // インデックス ix の値を x, y に変更する
    void set(int ix, int x, int y) {
        if (ix >= 0 && ix < length) {
            xs[ix] = x;
            ys[ix] = y;
        } else {
            System.out.printf("set: error ix=%d x=%d y=%d\n", ix, x, y);
        }
    }

    void add(int x, int y) {    // 末尾に追加
        if (length < size) {
            xs[length] = x;
            ys[length] = y;
            length++;
        } else {
            System.out.printf("add: error length=%d x=%d y=%d\n", length, x, y);
        }
    }

    // from は含む、to は含まない
    void add(Polygon poly, int from, int to) {
        if (length + (to - from) <= size) {
            for (int i = from; i < to; i++) {
                xs[length] = poly.xs[i];
                ys[length] = poly.ys[i];
                length++;
            }
        } else {
            System.out.printf("add: error length=%d from=%d to=%d\n", length, from, to);
        }
    }


    // from は含む、to は含まない
    void remove(int from, int to) {
        if (from > to || to > length) {
            System.out.printf("remove: error length=%d from=%d to=%d\n", length, from, to);
            return;
        }
        System.arraycopy(xs, to, xs, from, length-to);
        System.arraycopy(ys, to, ys, from, length-to);
        length -= to - from;
    }

    static int crossHorizonX(int x1, int y1, int x2, int y2, int y) {
        return x1 + (int)( ((long)x2 - x1) * (y - y1) / (y2 - y1) );
    }

    static int crossVertY(int x1, int y1, int x2, int y2, int x) {
        //return y1 + (int)( ((long)y2 - y1) * (x - x1) / (x2 - x1) );
        return y1 + (int)( ((long)y2 - y1) * (x - x1) / (x2 - x1) );
    }


    List<Polygon> splitPolygon(int span) {
        List<Polygon> listOut = new ArrayList<>();
        List<Polygon> list =  splitPolygonVertically(span);
        for (Polygon poly : list) {
            listOut.addAll(poly.splitPolygonHorizontally(span));
        }
        return listOut;
    }


    List<Polygon> splitPolygonHorizontally(int span) {
        List<Polygon> dst = new ArrayList<>();

        rotate(iYmax);  //System.out.printf("iYmax=%d\n", iYmax);
        int bgn = ((ymin + span) / span) * span;
        boolean fSplit = false;
        for (int y = bgn; y < ymax; y += span) {  // y : 水平分割線のY座標
            int cntCross = 0;
            int i1 = -1, i2 = -1;
            int k = iYmax;
            do {
                if ((ys[k] - (long)y) * (ys[next(k)] - y) < 0) {  // 交差判定
                    cntCross++;
                    if (i1 < 0) i1 = k;     // 最初の交点
                    else i2 = k;            // 最後の交点
                } 
                k = next(k);
            } while (k != iYmax) ;          // 一巡するまで

            //System.out.printf("%d ", cntCross);
            if (cntCross == 2 && i2 - i1 >= 2 && i2+1 < xs.length) { // 水平分割可能
                if ((ys[i1] == y && ys[next(i1)] == y) || (ys[i2] == y && ys[next(i2)] == y)) {
                    System.out.printf("Skip\n");
                    continue;
                }

                int x1 = crossHorizonX(xs[i1], ys[i1], xs[next(i1)], ys[next(i1)], y);
                int x2 = crossHorizonX(xs[i2], ys[i2], xs[next(i2)], ys[next(i2)], y);
                // (x1,y): 線分i1ーi1+1と水平線yの交点, (x2,y): 線分i2ーi2+1と水平線yの交点
                if (x2 > x1) {
                    System.out.printf("Error x1=%d x2=%d\n", x1, x2);
                    continue;   // 分割しない
                }

                //分割で生まれるポリゴン x1, i1+1, ... , i2, x2, x1
                Polygon pN = new Polygon(i2 - i1 + 3);
                pN.add(x1, y);
                for (int i = i1+1; i <= i2; i++) {
                    pN.add(xs[i], ys[i]);
                }
                pN.add(x2, y);
                pN.add(x1, y);
                pN.setMinMax();
                pN.fSplit = true;
                fSplit = true;      // 分割が起きた
   //System.out.printf("assign=%d length=%d\n", i2 - i1 + 3, pN.length); ここでの矛盾はない

                dst.add(pN);

                // 元のポリゴン(小さくなる)
                set(i1+1, x1, y);
                set(i2, x2, y);
                remove(i1+2, i2);  // i1+2, i1+3, ... , i2-1 を削除
                setMinMax();
            }
            //System.out.println();
        }
        setMinMax();
        dst.add(this);
        return dst;
    }


    List<Polygon> splitPolygonVertically(int span) {
        List<Polygon> dst = new ArrayList<>();

        rotate(iXmax);  //System.out.printf("iXmax=%d\n", iXmax);
        int bgn = ((xmin + span) / span) * span;
        boolean fSplit = false;
        for (int x = bgn; x < xmax; x += span) {  // x : 垂直分割線のX座標
            int cntCross = 0;
            int i1 = -1, i2 = -1;
            int k = iXmax;
            do {
                if ((xs[k] - (long)x) * (xs[next(k)] - x) < 0) {  // 交差判定
                    cntCross++;
                    if (i1 < 0) i1 = k;     // 最初の交点
                    else i2 = k;            // 最後の交点
                } 
                k = next(k);
            } while (k != iXmax) ;          // 一巡するまで

            //System.out.printf("%d ", cntCross);
            if (cntCross == 2 && i2 - i1 >= 2 && i2+1 < ys.length) { // 垂直分割可能
                if ((xs[i1] == x && xs[next(i1)] == x) || (xs[i2] == x && xs[next(i2)] == x)) {
                    System.out.printf("Skip\n");
                    continue;
                }
                int y1 = crossVertY(xs[i1], ys[i1], xs[next(i1)], ys[next(i1)], x);
                int y2 = crossVertY(xs[i2], ys[i2], xs[next(i2)], ys[next(i2)], x);
                // (x,y1): 線分i1ーi1+1と水平線yの交点, (x,y2): 線分i2ーi2+1と垂直線xの交点
                if (y2 < y1) {
                    System.out.printf("Err x=%d(%.4f) y1=%d y2=%d \tX(%.6f〜%.6f) Y(%.6f〜%.6f) i1=%d i2=%d iXmax=%d len=%d\n", 
                            x, x/B30,   y1, y2, xs[i2]/B30, xs[i2+1]/B30, ys[i2]/B30, ys[i2+1]/B30, i1, i2, iXmax, length);
                    continue;   // 分割しない
                }

                //分割で生まれるポリゴン y1, i1+1, ... , i2, y2, y1
                Polygon pN = new Polygon(i2 - i1 + 3);
                pN.add(x, y1);
                for (int i = i1+1; i <= i2; i++) {
                    pN.add(xs[i], ys[i]);
                }
                pN.add(x, y2);
                pN.add(x, y1);
                pN.setMinMax();
                pN.fSplit = true;
                fSplit = true;      // 分割が起きた
   //System.out.printf("assign=%d length=%d\n", i2 - i1 + 3, pN.length); ここでの矛盾はない

                dst.add(pN);

                // 元のポリゴン(小さくなる)
                set(i1+1, x, y1);
                set(i2, x, y2);
                remove(i1+2, i2);  // i1+2, i1+3, ... , i2-1 を削除
                setMinMax();
            }
            //System.out.println();
        }
        setMinMax();
        dst.add(this);
        return dst;
    }

    // newStart が配列の先頭になるように回転する
    void rotate(int newStart) {
        int[] xsNew = xs.clone();
        int[] ysNew = ys.clone();
        for (int i = 0; i < length; i++) {
            xsNew[i] = xs[(i+newStart)%length];
            ysNew[i] = ys[(i+newStart)%length];
        }
        xs = xsNew;
        ys = ysNew;
        iXmax = (iXmax + length - newStart) % length;
        iYmax = (iYmax + length - newStart) % length;
    }

    void reverse(int[] array) {
        for (int left=0, right=array.length-1; left < right; ) {
            int temp = array[left];
            array[left++] = array[right];
            array[right--] = temp;
        }
    }

    // ノードを間引く shrink
    void shrink(double epsilon) {
        SimplifySection(xs, ys, 0, length-1, epsilon);
        int dst = 0;
        for (int src = 0; src < length; src++) {
            if (xs[src] > Integer.MIN_VALUE) {
                xs[dst] = xs[src];
                ys[dst] = ys[src];
                dst++;
            }
        }
        length = dst;
    }


    //SimplifySection(xs, ys, 0, xs.length-2, 10000); // 100m
    void SimplifySection(int[] xs, int[] ys, int i, int j, double epsilon) {
        if ((i + 1) == j) return;
        double maxDistance = -1.0;
        int maxIndex = i;
        for (int k = i + 1; k < j; k++) {
            double distance = PerpendicularDistance(xs[k], ys[k], xs[i], ys[i], xs[j], ys[j]);
            if (distance > maxDistance) {
                maxDistance = distance;
                maxIndex = k;
            }
        }
        if (maxDistance <= epsilon) {
            for (int k = i + 1; k < j; k++) {
                xs[k] = Integer.MIN_VALUE;   // 間引く
                ys[k] = Integer.MIN_VALUE;   // 間引く
            }
        } else {
            SimplifySection(xs, ys, i, maxIndex, epsilon);
            SimplifySection(xs, ys, maxIndex, j, epsilon);
        }
    }

    // １度＝約100km ⇒ 1m＝約0.00001度
    double PerpendicularDistance(double px, double py, double p1x, double p1y, double p2x, double p2y) {
        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;
    }


    static byte[] ba = new byte[128*1024*1024];
    // 
    void writePolygon(DataOutputStream dos) throws Exception {
//System.out.println("writePolygon");
        ByteBuffer bb = ByteBuffer.wrap(ba);
        bb.putInt(xmin);
        bb.putInt(ymin);
        bb.putInt(xmax);
        bb.putInt(ymax);
        bb.putInt(-1);          // rid
        bb.putLong(0L);         // osm_id
        bb.putFloat(Math.abs((float)calcWayArea()));
        bb.putInt(Tag.Key.natural.ordinal());
        bb.putInt(Tag.Val.land.ordinal());
        bb.putInt(length+1);   // ノード数
        for (int k = 0; k < length; k++) {
            bb.putInt(xs[k]);
            bb.putInt(ys[k]);
        }
        bb.putInt(xs[0]);       // 末尾に先頭と同じ値を追加
        bb.putInt(ys[0]);       // 同上

        int rec_length = bb.position(); // バイト単位
        try {
            int head = 0x02 | 0x20;     // polygon かつ Mapアプリ型データ
            if (fSplit) head |= 0x40;
            dos.writeInt(head);
            dos.writeInt(rec_length);
            dos.write(ba, 0, bb.position());
        } catch (Exception e) {
            e.printStackTrace();
        }
    }


    // ポリゴンの面積を計算する。単位は �u である。
    double calcWayArea() {
        double Radius = 6378137 + 100;      // 長半径 + 楕円高（仮）
        double[] lons = new double[length];
        double[] lats = new double[length];
        for (int n = 0; n < length; n++) {
            lons[n] = X2Lon(xs[n], 0)*Math.PI/180.0;   // ラジアンに変換;
            lats[n] = Y2Lat(ys[n], 0)*Math.PI/180.0;   // ラジアンに変換;
        }
        double wayarea = 0;
        var lon1 = lons[length-1];      // 最後のノード
        var lat1 = lats[length-1];
        for (int n = 0; n < length; n++) {
            var lon2 = lons[n];
            var lat2 = lats[n];
            wayarea += (lon2-lon1)*(2+Math.sin(lat1)+Math.sin(lat2));
            lon1 = lon2;
            lat1 = lat2;
        }
        return wayarea * Radius * Radius / 2.0;
    }   // 反時計回りが負、時計回りは正となる


    double X2Lon(int x, int zoom) {
        return X2Lon((double)x / (1<<30), zoom);
    }

    double Y2Lat(int y, int zoom) {
        return Y2Lat((double)y / (1<<30), zoom);
    }

    double X2Lon(double x, int z) {
        return x / Math.pow(2.0, z) * 360.0 - 180.0;
    }

    double Y2Lat(double y, int z) {
        double n = Math.PI - (2.0 * Math.PI * y) / Math.pow(2.0, z);
        return 180.0 / Math.PI * Math.atan(Math.sinh(n));
    }
}