#include <bits/stdc++.h>
#include "jngen.h"
using namespace std;
#define forn(i, n) for (int i = 0; i < int(n); ++i)

jngen::Dsu dsu;

int n = 1000;
vector<Point> p;

double dist(Point x, Point y) {
    double dx = x.x - y.x;
    double dy = x.y - y.y;
    return sqrt(dx*dx+dy*dy);
}

vector<vector<int>> e;
vector<int> b;
vector<int> res;

void dfs(int v) {
    b[v] = 1;
    res.push_back(v);
    for (int to: e[v]) {
        if (!b[to]) dfs(to);
    }
}

bool intersect(int l1, int r1, int l2, int r2) {
    return max(l1, l2) <= min(r1, r2);
}

bool segmentsIntersect(Point a, Point b, Point c, Point d) {
    if (!intersect(min(a.x, b.x), max(a.x, b.x), min(c.x, d.x), max(c.x, d.x))) return false;
    if (!intersect(min(a.y, b.y), max(a.y, b.y), min(c.y, d.y), max(c.y, d.y))) return false;
    for (int i = 0; i < 2; ++i) {
        long long s1 = (c-a) % (b-a);
        long long s2 = (d-a) % (b-a);
        assert(s1 != 0 && s2 != 0);
        if ((s1 < 0) == (s2 < 0)) return false;
    }
    return true;
}

vector<Point> runFix(vector<Point> p) {
    bool done = true;
    int n = p.size();
    while (done) {
        cerr << "Fixing..." << endl;
        done = false;
        for (int i = 0; i < n; ++i) {
            for (int j = i+2; j < n; ++j) {
                if ((j+1)%n == i) continue;
                if (segmentsIntersect(p[i], p[i+1], p[j], p[(j+1)%n])) {
                    reverse(p.begin() + i + 1, p.begin() + j + 1);
                    done = true;
                }
            }
        }
    }
    return p;
}

int main(int argc, char *argv[]) {
    // registerGen(argc, argv);
    parseArgs(argc, argv);

    p = rndg.pointsInGeneralPosition(n, 100000).shuffled();
    vector<pair<int, int>> es;
    forn(i, n) forn(j, i) es.emplace_back(i, j);
    sort(es.begin(), es.end(), [&](pair<int, int> x, pair<int, int> y) {
        return dist(p[x.first], p[x.second]) < dist(p[y.first], p[y.second]);
    });
    e.resize(n);
    b.resize(n);
    for (auto ee: es) {
        int x, y;
        tie(x, y) = ee;
        if (dsu.unite(x, y)) {
            e[x].push_back(y);
            e[y].push_back(x);
        }
    }
    mt19937 rr;
    forn(i, n) shuffle(e[i].begin(), e[i].end());
    dfs(0);

    // Uncomment this line to try random order instead of MST order.
    // res = Array::id(n).shuffle();

    res.push_back(res[0]);

    Drawer d;
    for (auto pp: p) d.point(pp);
    forn(i, n) d.segment(p[res[i]], p[res[i+1]]);
    d.dumpSvg("image.svg");

    vector<Point> fixed;
    forn(i, n) fixed.push_back(p[res[i]]);
    fixed = runFix(fixed);

    d = Drawer();
    for (auto pp: p) d.point(pp);
    forn(i, n) d.segment(fixed[i], fixed[(i+1)%n]);
    d.dumpSvg("image_fixed.svg");
}