// line_symmetry.cpp --- 多角形が線対称かどうか判定する。
// Copyright (C) 2013 片山博文MZ. All rights reserved.
#include <iostream>
#include <vector>
#include <cstdlib>
#include <cstring>
#include <cmath>
using namespace std;
 
// 実数型。
typedef double numeric_t;
 
// 位置ベクトルの比較の際の許容される誤差。
const numeric_t TOLERANCE1 = 0.25;
 
// 単位ベクトルの比較の際の許容される誤差。
const numeric_t TOLERANCE2 = 0.015625;
 
// 平面ベクトル。
class Point2D
{
public:
    numeric_t m_x, m_y;
 
public:
    Point2D()
    {
    }
    Point2D(numeric_t x, numeric_t y) : m_x(x), m_y(y)
    {
    }
    Point2D(const Point2D& p) : m_x(p.m_x), m_y(p.m_y)
    {
    }
 
    void GetXY(numeric_t& x, numeric_t& y) const
    {
        x = m_x; y = m_y;
    }
    void SetXY(numeric_t x, numeric_t y)
    {
        m_x = x; m_y = y;
    }
    bool IsZero() const
    {
        return Length() <= TOLERANCE1;
    }
    void SetZero()
    {
        m_x = m_y = 0;
    }
 
    // 長さ。
    numeric_t Length() const
    {
        return sqrt(m_x * m_x + m_y * m_y);
    }
    // 垂直なベクトル。
    Point2D Perpendicular() const
    {
        return Point2D(m_y, -m_x);
    }
    // 単位ベクトル。
    Point2D Unit() const
    {
        return *this / Length();
    }
 
    Point2D& operator=(const Point2D& p)
    {
        m_x = p.m_x; m_y = p.m_y;
        return *this;
    }
    Point2D& operator+=(const Point2D& p)
    {
        m_x += p.m_x; m_y += p.m_y;
        return *this;
    }
    Point2D& operator-=(const Point2D& p)
    {
        m_x -= p.m_x; m_y -= p.m_y;
        return *this;
    }
    Point2D& operator*=(numeric_t d)
    {
        m_x *= d; m_y *= d;
        return *this;
    }
    Point2D& operator/=(numeric_t d)
    {
        m_x /= d; m_y /= d;
        return *this;
    }
 
    friend Point2D operator+(const Point2D& p1, const Point2D& p2)
    {
        Point2D p(p1);
        p += p2;
        return p;
    }
    friend Point2D operator-(const Point2D& p1, const Point2D& p2)
    {
        Point2D p(p1);
        p -= p2;
        return p;
    }
 
    friend bool operator==(const Point2D& p1, const Point2D& p2)
    {
        numeric_t dx = p2.m_x - p1.m_x, dy = p2.m_y - p1.m_y;
        return sqrt(dx * dx + dy * dy) <= TOLERANCE1;
    }
    friend bool operator!=(const Point2D& p1, const Point2D& p2)
    {
        return !(p1 == p2);
    }
 
    friend numeric_t operator*(const Point2D& p1, const Point2D& p2)
    {
        return p1.m_x * p2.m_x + p1.m_y * p2.m_y;
    }
 
    friend Point2D operator*(const Point2D& p1, numeric_t d)
    {
        Point2D p(p1);
        p *= d;
        return p;
    }
    friend Point2D operator/(const Point2D& p1, numeric_t d)
    {
        Point2D p(p1);
        p /= d;
        return p;
    }
    friend Point2D operator*(numeric_t d, const Point2D& p1)
    {
        return p1 * d;
    }
 
    // 中点。
    friend Point2D MidPoint(const Point2D& p1, const Point2D& p2)
    {
        return Point2D((p1.m_x + p2.m_x) / 2, (p1.m_y + p2.m_y) / 2);
    }
 
    friend ostream& operator<<(ostream& o, const Point2D& p)
    {
        o << "(" << p.m_x << ", " << p.m_y << ")";
        return o;
    }
 
    // 一直線上にあるかどうか？
    friend bool OnOneLine(const Point2D& p1, const Point2D& p2, const Point2D& p3)
    {
        return ((p2 - p1).Unit() - (p3 - p2).Unit()).Length() <= TOLERANCE2;
    }
};
 
int main(void)
{
    int i, j, n, i1, i2;
    numeric_t x, y, g;
    Point2D mp, unit, p1, p2, p3, q, r;
    vector<Point2D> polygon;
    bool f;
 
    // 入力。
    cout << "多角形の頂点の個数: ";
    cin >> n;
    if (n < 0)
    {
        cout << "データが不正です。" << endl;
        return 1;
    }
    for (i = 0; i < n; i++)
    {
        cout << "頂点#" << (i + 1) << "のx座標とy座標: ";
        cin >> x >> y;
        polygon.push_back(Point2D(x, y));
    }
 
    // 重複した頂点を取り除く。
    f = false;
    for (i = 0; i < n - 1; i++)
    {
        p1 = polygon[i];
        p2 = polygon[i + 1];
        if (p1 == p2)
        {
            memmove(&polygon[i], &polygon[i + 1], (n - i - 1) * sizeof(Point2D));
            polygon.resize(--n);
            i--;
            f = true;
        }
    }
    if (n > 1)
    {
        p1 = polygon[n - 1];
        p2 = polygon[0];
        if (p1 == p2)
        {
            polygon.resize(--n);
            f = true;
        }
    }
    if (f)
        cout << "重複した頂点を取り除きました。" << endl;
 
    // 約180度の角の頂点を取り除く。
    f = false;
    for (i = 0; i < n - 2; i++)
    {
        p1 = polygon[i];
        p2 = polygon[i + 1];
        p3 = polygon[i + 2];
        if (OnOneLine(p1, p2, p3))
        {
            memmove(&polygon[i + 1], &polygon[i + 2], (n - i - 2) * sizeof(Point2D));
            polygon.resize(--n);
            i--;
            f = true;
        }
    }
    while (n > 2)
    {
        p1 = polygon[n - 2];
        p2 = polygon[n - 1];
        p3 = polygon[0];
        if (OnOneLine(p1, p2, p3))
        {
            polygon.resize(--n);
            f = true;
            continue;
        }
        break;
    }
    while (n > 2)
    {
        p1 = polygon[n - 1];
        p2 = polygon[0];
        p3 = polygon[1];
        if (OnOneLine(p1, p2, p3))
        {
            memmove(&polygon[0], &polygon[1], (n - 1) * sizeof(Point2D));
            polygon.resize(--n);
            f = true;
            continue;
        }
        break;
    }
    if (f)
        cout << "約180度の角の頂点を取り除きました。" << endl;
 
    // 表示。
    if (n > 0)
    {
        for (i = 0; i < n; i++)
        {
            cout << "頂点#" << (i + 1) << ": " << polygon[i] << endl;
        }
    }
    else
    {
        cout << "頂点はありません。" << endl;
    }
 
    // ０角形、１角形、２角形は、常に線対称。
    if (n <= 2)
    {
        cout << "頂点が2個以下なので線対称です。" << endl;
        return 0;
    }
 
    // 頂点の角の二等分線が対称の軸か？
    for (i = 0; i < n; i++)
    {
        // 隣り合う３頂点。
        p1 = polygon[(i - 1 + n) % n];
        p2 = polygon[i];
        p3 = polygon[(i + 1) % n];
 
        // 角に隣り合う２辺の長さが等しいか？
        if (fabs((p2 - p1).Length() - (p3 - p2).Length()) <= TOLERANCE1)
        {
            // 角に隣り合う２頂点の中点。
            mp = MidPoint(p1, p3);
 
            // 角の二等分線に平行な単位ベクトル。
            if ((mp - p2).IsZero())
                unit = (p3 - p1).Perpendicular().Unit();
            else
                unit = (mp - p2).Unit();
 
            f = true;
            for (j = 1; j <= n / 2; j++)
            {
                // 対称か判定する２頂点のインデックス。
                i1 = (i - j + n) % n;
                i2 = (i + j) % n;
 
                g = (polygon[i1] - mp) * unit;      // 中点から垂線までの長さ。
                q = mp + unit * g;                  // 対称の軸上の点（垂線と交わる）。
                r = q - (polygon[i1] - q);          // 軸に対して対称な位置。
                //cout << "1%%" << (r - polygon[i2]).Length() << endl;
                if (r != polygon[i2])
                {
                    f = false;
                    break;
                }
            }
 
            if (f)
            {
                cout << "頂点#" << (i + 1) << "で線対称です。" << endl;
                return 0;
            }
        }
    }
 
    // 辺の垂直二等分線が対称の軸か？
    for (i = 0; i < n; i++)
    {
        // 隣り合う２頂点。
        p1 = polygon[i];
        p2 = polygon[(i + 1) % n];
 
        // 辺の中点。
        mp = MidPoint(p1, p2);
 
        // 辺に対する垂直単位ベクトル。
        if ((p2 - p1).Perpendicular().IsZero())
            unit.SetZero();
        else
            unit = (p2 - p1).Perpendicular().Unit();
 
        f = true;
        for (j = 1; j < (n + 1) / 2; j++)
        {
            // 対称か判定する２頂点のインデックス。
            i1 = (i - j + n) % n;
            i2 = (i + j + 1) % n;
 
            g = (polygon[i1] - mp) * unit;          // 中点から垂線までの長さ。
            q = mp + unit * g;                      // 対称の軸上の点（垂線と交わる）。
            r = q - (polygon[i1] - q);              // 軸に対して対称な位置。
            //cout << "2%%" << (r - polygon[i2]).Length() << endl;
            if (r != polygon[i2])
            {
                f = false;
                break;
            }
        }
 
        if (f)
        {
            cout << "頂点#" << (i + 1) << "と頂点#" << ((i + 1) % n + 1) <<
                "の間で線対称です。" << endl;
            return 0;
        }
    }
 
    cout << "線対称ではありません。" << endl;
    return 0;
}

Ly8gbGluZV9zeW1tZXRyeS5jcHAgLS0tIOWkmuinkuW9ouOBjOe3muWvvuensOOBi+OBqeOBhuOBi+WIpOWumuOBmeOCi+OAggovLyBDb3B5cmlnaHQgKEMpIDIwMTMg54mH5bGx5Y2a5paHTVouIEFsbCByaWdodHMgcmVzZXJ2ZWQuCiNpbmNsdWRlIDxpb3N0cmVhbT4KI2luY2x1ZGUgPHZlY3Rvcj4KI2luY2x1ZGUgPGNzdGRsaWI+CiNpbmNsdWRlIDxjc3RyaW5nPgojaW5jbHVkZSA8Y21hdGg+CnVzaW5nIG5hbWVzcGFjZSBzdGQ7CgovLyDlrp/mlbDlnovjgIIKdHlwZWRlZiBkb3VibGUgbnVtZXJpY190OwoKLy8g5L2N572u44OZ44Kv44OI44Or44Gu5q+U6LyD44Gu6Zqb44Gu6Kix5a6544GV44KM44KL6Kqk5beu44CCCmNvbnN0IG51bWVyaWNfdCBUT0xFUkFOQ0UxID0gMC4yNTsKCi8vIOWNmOS9jeODmeOCr+ODiOODq+OBruavlOi8g+OBrumam+OBruioseWuueOBleOCjOOCi+iqpOW3ruOAggpjb25zdCBudW1lcmljX3QgVE9MRVJBTkNFMiA9IDAuMDE1NjI1OwoKLy8g5bmz6Z2i44OZ44Kv44OI44Or44CCCmNsYXNzIFBvaW50MkQKewpwdWJsaWM6CiAgICBudW1lcmljX3QgbV94LCBtX3k7CgpwdWJsaWM6CiAgICBQb2ludDJEKCkKICAgIHsKICAgIH0KICAgIFBvaW50MkQobnVtZXJpY190IHgsIG51bWVyaWNfdCB5KSA6IG1feCh4KSwgbV95KHkpCiAgICB7CiAgICB9CiAgICBQb2ludDJEKGNvbnN0IFBvaW50MkQmIHApIDogbV94KHAubV94KSwgbV95KHAubV95KQogICAgewogICAgfQoKICAgIHZvaWQgR2V0WFkobnVtZXJpY190JiB4LCBudW1lcmljX3QmIHkpIGNvbnN0CiAgICB7CiAgICAgICAgeCA9IG1feDsgeSA9IG1feTsKICAgIH0KICAgIHZvaWQgU2V0WFkobnVtZXJpY190IHgsIG51bWVyaWNfdCB5KQogICAgewogICAgICAgIG1feCA9IHg7IG1feSA9IHk7CiAgICB9CiAgICBib29sIElzWmVybygpIGNvbnN0CiAgICB7CiAgICAgICAgcmV0dXJuIExlbmd0aCgpIDw9IFRPTEVSQU5DRTE7CiAgICB9CiAgICB2b2lkIFNldFplcm8oKQogICAgewogICAgICAgIG1feCA9IG1feSA9IDA7CiAgICB9CgogICAgLy8g6ZW344GV44CCCiAgICBudW1lcmljX3QgTGVuZ3RoKCkgY29uc3QKICAgIHsKICAgICAgICByZXR1cm4gc3FydChtX3ggKiBtX3ggKyBtX3kgKiBtX3kpOwogICAgfQogICAgLy8g5Z6C55u044Gq44OZ44Kv44OI44Or44CCCiAgICBQb2ludDJEIFBlcnBlbmRpY3VsYXIoKSBjb25zdAogICAgewogICAgICAgIHJldHVybiBQb2ludDJEKG1feSwgLW1feCk7CiAgICB9CiAgICAvLyDljZjkvY3jg5njgq/jg4jjg6vjgIIKICAgIFBvaW50MkQgVW5pdCgpIGNvbnN0CiAgICB7CiAgICAgICAgcmV0dXJuICp0aGlzIC8gTGVuZ3RoKCk7CiAgICB9CgogICAgUG9pbnQyRCYgb3BlcmF0b3I9KGNvbnN0IFBvaW50MkQmIHApCiAgICB7CiAgICAgICAgbV94ID0gcC5tX3g7IG1feSA9IHAubV95OwogICAgICAgIHJldHVybiAqdGhpczsKICAgIH0KICAgIFBvaW50MkQmIG9wZXJhdG9yKz0oY29uc3QgUG9pbnQyRCYgcCkKICAgIHsKICAgICAgICBtX3ggKz0gcC5tX3g7IG1feSArPSBwLm1feTsKICAgICAgICByZXR1cm4gKnRoaXM7CiAgICB9CiAgICBQb2ludDJEJiBvcGVyYXRvci09KGNvbnN0IFBvaW50MkQmIHApCiAgICB7CiAgICAgICAgbV94IC09IHAubV94OyBtX3kgLT0gcC5tX3k7CiAgICAgICAgcmV0dXJuICp0aGlzOwogICAgfQogICAgUG9pbnQyRCYgb3BlcmF0b3IqPShudW1lcmljX3QgZCkKICAgIHsKICAgICAgICBtX3ggKj0gZDsgbV95ICo9IGQ7CiAgICAgICAgcmV0dXJuICp0aGlzOwogICAgfQogICAgUG9pbnQyRCYgb3BlcmF0b3IvPShudW1lcmljX3QgZCkKICAgIHsKICAgICAgICBtX3ggLz0gZDsgbV95IC89IGQ7CiAgICAgICAgcmV0dXJuICp0aGlzOwogICAgfQoKICAgIGZyaWVuZCBQb2ludDJEIG9wZXJhdG9yKyhjb25zdCBQb2ludDJEJiBwMSwgY29uc3QgUG9pbnQyRCYgcDIpCiAgICB7CiAgICAgICAgUG9pbnQyRCBwKHAxKTsKICAgICAgICBwICs9IHAyOwogICAgICAgIHJldHVybiBwOwogICAgfQogICAgZnJpZW5kIFBvaW50MkQgb3BlcmF0b3ItKGNvbnN0IFBvaW50MkQmIHAxLCBjb25zdCBQb2ludDJEJiBwMikKICAgIHsKICAgICAgICBQb2ludDJEIHAocDEpOwogICAgICAgIHAgLT0gcDI7CiAgICAgICAgcmV0dXJuIHA7CiAgICB9CgogICAgZnJpZW5kIGJvb2wgb3BlcmF0b3I9PShjb25zdCBQb2ludDJEJiBwMSwgY29uc3QgUG9pbnQyRCYgcDIpCiAgICB7CiAgICAgICAgbnVtZXJpY190IGR4ID0gcDIubV94IC0gcDEubV94LCBkeSA9IHAyLm1feSAtIHAxLm1feTsKICAgICAgICByZXR1cm4gc3FydChkeCAqIGR4ICsgZHkgKiBkeSkgPD0gVE9MRVJBTkNFMTsKICAgIH0KICAgIGZyaWVuZCBib29sIG9wZXJhdG9yIT0oY29uc3QgUG9pbnQyRCYgcDEsIGNvbnN0IFBvaW50MkQmIHAyKQogICAgewogICAgICAgIHJldHVybiAhKHAxID09IHAyKTsKICAgIH0KCiAgICBmcmllbmQgbnVtZXJpY190IG9wZXJhdG9yKihjb25zdCBQb2ludDJEJiBwMSwgY29uc3QgUG9pbnQyRCYgcDIpCiAgICB7CiAgICAgICAgcmV0dXJuIHAxLm1feCAqIHAyLm1feCArIHAxLm1feSAqIHAyLm1feTsKICAgIH0KCiAgICBmcmllbmQgUG9pbnQyRCBvcGVyYXRvciooY29uc3QgUG9pbnQyRCYgcDEsIG51bWVyaWNfdCBkKQogICAgewogICAgICAgIFBvaW50MkQgcChwMSk7CiAgICAgICAgcCAqPSBkOwogICAgICAgIHJldHVybiBwOwogICAgfQogICAgZnJpZW5kIFBvaW50MkQgb3BlcmF0b3IvKGNvbnN0IFBvaW50MkQmIHAxLCBudW1lcmljX3QgZCkKICAgIHsKICAgICAgICBQb2ludDJEIHAocDEpOwogICAgICAgIHAgLz0gZDsKICAgICAgICByZXR1cm4gcDsKICAgIH0KICAgIGZyaWVuZCBQb2ludDJEIG9wZXJhdG9yKihudW1lcmljX3QgZCwgY29uc3QgUG9pbnQyRCYgcDEpCiAgICB7CiAgICAgICAgcmV0dXJuIHAxICogZDsKICAgIH0KCiAgICAvLyDkuK3ngrnjgIIKICAgIGZyaWVuZCBQb2ludDJEIE1pZFBvaW50KGNvbnN0IFBvaW50MkQmIHAxLCBjb25zdCBQb2ludDJEJiBwMikKICAgIHsKICAgICAgICByZXR1cm4gUG9pbnQyRCgocDEubV94ICsgcDIubV94KSAvIDIsIChwMS5tX3kgKyBwMi5tX3kpIC8gMik7CiAgICB9CgogICAgZnJpZW5kIG9zdHJlYW0mIG9wZXJhdG9yPDwob3N0cmVhbSYgbywgY29uc3QgUG9pbnQyRCYgcCkKICAgIHsKICAgICAgICBvIDw8ICIoIiA8PCBwLm1feCA8PCAiLCAiIDw8IHAubV95IDw8ICIpIjsKICAgICAgICByZXR1cm4gbzsKICAgIH0KCiAgICAvLyDkuIDnm7Tnt5rkuIrjgavjgYLjgovjgYvjganjgYbjgYvvvJ8KICAgIGZyaWVuZCBib29sIE9uT25lTGluZShjb25zdCBQb2ludDJEJiBwMSwgY29uc3QgUG9pbnQyRCYgcDIsIGNvbnN0IFBvaW50MkQmIHAzKQogICAgewogICAgICAgIHJldHVybiAoKHAyIC0gcDEpLlVuaXQoKSAtIChwMyAtIHAyKS5Vbml0KCkpLkxlbmd0aCgpIDw9IFRPTEVSQU5DRTI7CiAgICB9Cn07CgppbnQgbWFpbih2b2lkKQp7CiAgICBpbnQgaSwgaiwgbiwgaTEsIGkyOwogICAgbnVtZXJpY190IHgsIHksIGc7CiAgICBQb2ludDJEIG1wLCB1bml0LCBwMSwgcDIsIHAzLCBxLCByOwogICAgdmVjdG9yPFBvaW50MkQ+IHBvbHlnb247CiAgICBib29sIGY7CgogICAgLy8g5YWl5Yqb44CCCiAgICBjb3V0IDw8ICLlpJrop5LlvaLjga7poILngrnjga7lgIvmlbA6ICI7CiAgICBjaW4gPj4gbjsKICAgIGlmIChuIDwgMCkKICAgIHsKICAgICAgICBjb3V0IDw8ICLjg4fjg7zjgr/jgYzkuI3mraPjgafjgZnjgIIiIDw8IGVuZGw7CiAgICAgICAgcmV0dXJuIDE7CiAgICB9CiAgICBmb3IgKGkgPSAwOyBpIDwgbjsgaSsrKQogICAgewogICAgICAgIGNvdXQgPDwgIumggueCuSMiIDw8IChpICsgMSkgPDwgIuOBrnjluqfmqJnjgah55bqn5qiZOiAiOwogICAgICAgIGNpbiA+PiB4ID4+IHk7CiAgICAgICAgcG9seWdvbi5wdXNoX2JhY2soUG9pbnQyRCh4LCB5KSk7CiAgICB9CgogICAgLy8g6YeN6KSH44GX44Gf6aCC54K544KS5Y+W44KK6Zmk44GP44CCCiAgICBmID0gZmFsc2U7CiAgICBmb3IgKGkgPSAwOyBpIDwgbiAtIDE7IGkrKykKICAgIHsKICAgICAgICBwMSA9IHBvbHlnb25baV07CiAgICAgICAgcDIgPSBwb2x5Z29uW2kgKyAxXTsKICAgICAgICBpZiAocDEgPT0gcDIpCiAgICAgICAgewogICAgICAgICAgICBtZW1tb3ZlKCZwb2x5Z29uW2ldLCAmcG9seWdvbltpICsgMV0sIChuIC0gaSAtIDEpICogc2l6ZW9mKFBvaW50MkQpKTsKICAgICAgICAgICAgcG9seWdvbi5yZXNpemUoLS1uKTsKICAgICAgICAgICAgaS0tOwogICAgICAgICAgICBmID0gdHJ1ZTsKICAgICAgICB9CiAgICB9CiAgICBpZiAobiA+IDEpCiAgICB7CiAgICAgICAgcDEgPSBwb2x5Z29uW24gLSAxXTsKICAgICAgICBwMiA9IHBvbHlnb25bMF07CiAgICAgICAgaWYgKHAxID09IHAyKQogICAgICAgIHsKICAgICAgICAgICAgcG9seWdvbi5yZXNpemUoLS1uKTsKICAgICAgICAgICAgZiA9IHRydWU7CiAgICAgICAgfQogICAgfQogICAgaWYgKGYpCiAgICAgICAgY291dCA8PCAi6YeN6KSH44GX44Gf6aCC54K544KS5Y+W44KK6Zmk44GN44G+44GX44Gf44CCIiA8PCBlbmRsOwoKICAgIC8vIOe0hDE4MOW6puOBruinkuOBrumggueCueOCkuWPluOCiumZpOOBj+OAggogICAgZiA9IGZhbHNlOwogICAgZm9yIChpID0gMDsgaSA8IG4gLSAyOyBpKyspCiAgICB7CiAgICAgICAgcDEgPSBwb2x5Z29uW2ldOwogICAgICAgIHAyID0gcG9seWdvbltpICsgMV07CiAgICAgICAgcDMgPSBwb2x5Z29uW2kgKyAyXTsKICAgICAgICBpZiAoT25PbmVMaW5lKHAxLCBwMiwgcDMpKQogICAgICAgIHsKICAgICAgICAgICAgbWVtbW92ZSgmcG9seWdvbltpICsgMV0sICZwb2x5Z29uW2kgKyAyXSwgKG4gLSBpIC0gMikgKiBzaXplb2YoUG9pbnQyRCkpOwogICAgICAgICAgICBwb2x5Z29uLnJlc2l6ZSgtLW4pOwogICAgICAgICAgICBpLS07CiAgICAgICAgICAgIGYgPSB0cnVlOwogICAgICAgIH0KICAgIH0KICAgIHdoaWxlIChuID4gMikKICAgIHsKICAgICAgICBwMSA9IHBvbHlnb25bbiAtIDJdOwogICAgICAgIHAyID0gcG9seWdvbltuIC0gMV07CiAgICAgICAgcDMgPSBwb2x5Z29uWzBdOwogICAgICAgIGlmIChPbk9uZUxpbmUocDEsIHAyLCBwMykpCiAgICAgICAgewogICAgICAgICAgICBwb2x5Z29uLnJlc2l6ZSgtLW4pOwogICAgICAgICAgICBmID0gdHJ1ZTsKICAgICAgICAgICAgY29udGludWU7CiAgICAgICAgfQogICAgICAgIGJyZWFrOwogICAgfQogICAgd2hpbGUgKG4gPiAyKQogICAgewogICAgICAgIHAxID0gcG9seWdvbltuIC0gMV07CiAgICAgICAgcDIgPSBwb2x5Z29uWzBdOwogICAgICAgIHAzID0gcG9seWdvblsxXTsKICAgICAgICBpZiAoT25PbmVMaW5lKHAxLCBwMiwgcDMpKQogICAgICAgIHsKICAgICAgICAgICAgbWVtbW92ZSgmcG9seWdvblswXSwgJnBvbHlnb25bMV0sIChuIC0gMSkgKiBzaXplb2YoUG9pbnQyRCkpOwogICAgICAgICAgICBwb2x5Z29uLnJlc2l6ZSgtLW4pOwogICAgICAgICAgICBmID0gdHJ1ZTsKICAgICAgICAgICAgY29udGludWU7CiAgICAgICAgfQogICAgICAgIGJyZWFrOwogICAgfQogICAgaWYgKGYpCiAgICAgICAgY291dCA8PCAi57SEMTgw5bqm44Gu6KeS44Gu6aCC54K544KS5Y+W44KK6Zmk44GN44G+44GX44Gf44CCIiA8PCBlbmRsOwoKICAgIC8vIOihqOekuuOAggogICAgaWYgKG4gPiAwKQogICAgewogICAgICAgIGZvciAoaSA9IDA7IGkgPCBuOyBpKyspCiAgICAgICAgewogICAgICAgICAgICBjb3V0IDw8ICLpoILngrkjIiA8PCAoaSArIDEpIDw8ICI6ICIgPDwgcG9seWdvbltpXSA8PCBlbmRsOwogICAgICAgIH0KICAgIH0KICAgIGVsc2UKICAgIHsKICAgICAgICBjb3V0IDw8ICLpoILngrnjga/jgYLjgorjgb7jgZvjgpPjgIIiIDw8IGVuZGw7CiAgICB9CgogICAgLy8g77yQ6KeS5b2i44CB77yR6KeS5b2i44CB77yS6KeS5b2i44Gv44CB5bi444Gr57ea5a++56ew44CCCiAgICBpZiAobiA8PSAyKQogICAgewogICAgICAgIGNvdXQgPDwgIumggueCueOBjDLlgIvku6XkuIvjgarjga7jgafnt5rlr77np7DjgafjgZnjgIIiIDw8IGVuZGw7CiAgICAgICAgcmV0dXJuIDA7CiAgICB9CgogICAgLy8g6aCC54K544Gu6KeS44Gu5LqM562J5YiG57ea44GM5a++56ew44Gu6Lu444GL77yfCiAgICBmb3IgKGkgPSAwOyBpIDwgbjsgaSsrKQogICAgewogICAgICAgIC8vIOmao+OCiuWQiOOBhu+8k+mggueCueOAggogICAgICAgIHAxID0gcG9seWdvblsoaSAtIDEgKyBuKSAlIG5dOwogICAgICAgIHAyID0gcG9seWdvbltpXTsKICAgICAgICBwMyA9IHBvbHlnb25bKGkgKyAxKSAlIG5dOwoKICAgICAgICAvLyDop5LjgavpmqPjgorlkIjjgYbvvJLovrrjga7plbfjgZXjgYznrYnjgZfjgYTjgYvvvJ8KICAgICAgICBpZiAoZmFicygocDIgLSBwMSkuTGVuZ3RoKCkgLSAocDMgLSBwMikuTGVuZ3RoKCkpIDw9IFRPTEVSQU5DRTEpCiAgICAgICAgewogICAgICAgICAgICAvLyDop5LjgavpmqPjgorlkIjjgYbvvJLpoILngrnjga7kuK3ngrnjgIIKICAgICAgICAgICAgbXAgPSBNaWRQb2ludChwMSwgcDMpOwoKICAgICAgICAgICAgLy8g6KeS44Gu5LqM562J5YiG57ea44Gr5bmz6KGM44Gq5Y2Y5L2N44OZ44Kv44OI44Or44CCCiAgICAgICAgICAgIGlmICgobXAgLSBwMikuSXNaZXJvKCkpCiAgICAgICAgICAgICAgICB1bml0ID0gKHAzIC0gcDEpLlBlcnBlbmRpY3VsYXIoKS5Vbml0KCk7CiAgICAgICAgICAgIGVsc2UKICAgICAgICAgICAgICAgIHVuaXQgPSAobXAgLSBwMikuVW5pdCgpOwoKICAgICAgICAgICAgZiA9IHRydWU7CiAgICAgICAgICAgIGZvciAoaiA9IDE7IGogPD0gbiAvIDI7IGorKykKICAgICAgICAgICAgewogICAgICAgICAgICAgICAgLy8g5a++56ew44GL5Yik5a6a44GZ44KL77yS6aCC54K544Gu44Kk44Oz44OH44OD44Kv44K544CCCiAgICAgICAgICAgICAgICBpMSA9IChpIC0gaiArIG4pICUgbjsKICAgICAgICAgICAgICAgIGkyID0gKGkgKyBqKSAlIG47CgogICAgICAgICAgICAgICAgZyA9IChwb2x5Z29uW2kxXSAtIG1wKSAqIHVuaXQ7ICAgICAgLy8g5Lit54K544GL44KJ5Z6C57ea44G+44Gn44Gu6ZW344GV44CCCiAgICAgICAgICAgICAgICBxID0gbXAgKyB1bml0ICogZzsgICAgICAgICAgICAgICAgICAvLyDlr77np7Djga7ou7jkuIrjga7ngrnvvIjlnoLnt5rjgajkuqTjgo/jgovvvInjgIIKICAgICAgICAgICAgICAgIHIgPSBxIC0gKHBvbHlnb25baTFdIC0gcSk7ICAgICAgICAgIC8vIOi7uOOBq+WvvuOBl+OBpuWvvuensOOBquS9jee9ruOAggogICAgICAgICAgICAgICAgLy9jb3V0IDw8ICIxJSUiIDw8IChyIC0gcG9seWdvbltpMl0pLkxlbmd0aCgpIDw8IGVuZGw7CiAgICAgICAgICAgICAgICBpZiAociAhPSBwb2x5Z29uW2kyXSkKICAgICAgICAgICAgICAgIHsKICAgICAgICAgICAgICAgICAgICBmID0gZmFsc2U7CiAgICAgICAgICAgICAgICAgICAgYnJlYWs7CiAgICAgICAgICAgICAgICB9CiAgICAgICAgICAgIH0KCiAgICAgICAgICAgIGlmIChmKQogICAgICAgICAgICB7CiAgICAgICAgICAgICAgICBjb3V0IDw8ICLpoILngrkjIiA8PCAoaSArIDEpIDw8ICLjgafnt5rlr77np7DjgafjgZnjgIIiIDw8IGVuZGw7CiAgICAgICAgICAgICAgICByZXR1cm4gMDsKICAgICAgICAgICAgfQogICAgICAgIH0KICAgIH0KCiAgICAvLyDovrrjga7lnoLnm7TkuoznrYnliIbnt5rjgYzlr77np7Djga7ou7jjgYvvvJ8KICAgIGZvciAoaSA9IDA7IGkgPCBuOyBpKyspCiAgICB7CiAgICAgICAgLy8g6Zqj44KK5ZCI44GG77yS6aCC54K544CCCiAgICAgICAgcDEgPSBwb2x5Z29uW2ldOwogICAgICAgIHAyID0gcG9seWdvblsoaSArIDEpICUgbl07CgogICAgICAgIC8vIOi+uuOBruS4reeCueOAggogICAgICAgIG1wID0gTWlkUG9pbnQocDEsIHAyKTsKCiAgICAgICAgLy8g6L6644Gr5a++44GZ44KL5Z6C55u05Y2Y5L2N44OZ44Kv44OI44Or44CCCiAgICAgICAgaWYgKChwMiAtIHAxKS5QZXJwZW5kaWN1bGFyKCkuSXNaZXJvKCkpCiAgICAgICAgICAgIHVuaXQuU2V0WmVybygpOwogICAgICAgIGVsc2UKICAgICAgICAgICAgdW5pdCA9IChwMiAtIHAxKS5QZXJwZW5kaWN1bGFyKCkuVW5pdCgpOwoKICAgICAgICBmID0gdHJ1ZTsKICAgICAgICBmb3IgKGogPSAxOyBqIDwgKG4gKyAxKSAvIDI7IGorKykKICAgICAgICB7CiAgICAgICAgICAgIC8vIOWvvuensOOBi+WIpOWumuOBmeOCi++8kumggueCueOBruOCpOODs+ODh+ODg+OCr+OCueOAggogICAgICAgICAgICBpMSA9IChpIC0gaiArIG4pICUgbjsKICAgICAgICAgICAgaTIgPSAoaSArIGogKyAxKSAlIG47CgogICAgICAgICAgICBnID0gKHBvbHlnb25baTFdIC0gbXApICogdW5pdDsgICAgICAgICAgLy8g5Lit54K544GL44KJ5Z6C57ea44G+44Gn44Gu6ZW344GV44CCCiAgICAgICAgICAgIHEgPSBtcCArIHVuaXQgKiBnOyAgICAgICAgICAgICAgICAgICAgICAvLyDlr77np7Djga7ou7jkuIrjga7ngrnvvIjlnoLnt5rjgajkuqTjgo/jgovvvInjgIIKICAgICAgICAgICAgciA9IHEgLSAocG9seWdvbltpMV0gLSBxKTsgICAgICAgICAgICAgIC8vIOi7uOOBq+WvvuOBl+OBpuWvvuensOOBquS9jee9ruOAggogICAgICAgICAgICAvL2NvdXQgPDwgIjIlJSIgPDwgKHIgLSBwb2x5Z29uW2kyXSkuTGVuZ3RoKCkgPDwgZW5kbDsKICAgICAgICAgICAgaWYgKHIgIT0gcG9seWdvbltpMl0pCiAgICAgICAgICAgIHsKICAgICAgICAgICAgICAgIGYgPSBmYWxzZTsKICAgICAgICAgICAgICAgIGJyZWFrOwogICAgICAgICAgICB9CiAgICAgICAgfQoKICAgICAgICBpZiAoZikKICAgICAgICB7CiAgICAgICAgICAgIGNvdXQgPDwgIumggueCuSMiIDw8IChpICsgMSkgPDwgIuOBqOmggueCuSMiIDw8ICgoaSArIDEpICUgbiArIDEpIDw8CiAgICAgICAgICAgICAgICAi44Gu6ZaT44Gn57ea5a++56ew44Gn44GZ44CCIiA8PCBlbmRsOwogICAgICAgICAgICByZXR1cm4gMDsKICAgICAgICB9CiAgICB9CgogICAgY291dCA8PCAi57ea5a++56ew44Gn44Gv44GC44KK44G+44Gb44KT44CCIiA8PCBlbmRsOwogICAgcmV0dXJuIDA7Cn0=