Визуальный Коммивояжёр

#define map std_map
#include <bits/stdc++.h>
#include <SFML/Graphics.hpp>
#include <SFML/Window/ContextSettings.hpp>
#include <SFML/System/Time.hpp>
using namespace std;
using namespace sf;
#undef map

RenderWindow window;

const double I = 1.0 / 0.0;
const double X = 932;
const double Y = 932;

void check_event() {
    Event event;
    while (window.pollEvent(event)) {
        if (event.type == Event::Closed) {
            window.close();
        }
    }
}


void draw_point(int x, int y, Color c) {
    VertexArray pix(sf::Points, 1);
    pix[0].position = Vector2f(x, y);
    pix[0].color = c;
    window.draw(pix);
}

void draw_square(int x, int y, Color c) {
    const int S = 4;
    for (int i = 0; i < S; ++i) {
        for (int j = 0; j < S; ++j) {
            draw_point(22 + S * x + i, 22 + S * y + j, c);
        }
    }
}

void draw_line(int a, int b, int c, int d) {
    VertexArray l(sf::Lines, 2);
    l[0].position = Vector2f(a, b);
    l[1].position = Vector2f(c, d);
    l[0].color    = {0, 0, 0};
    l[1].color    = {0, 0, 0};
    window.draw(l);
}

void draw_circle(int x, int y, int r, Color c) {
    CircleShape a;
    a.setPosition(x - r, y - r);
    a.setRadius(r);
    a.setFillColor(c);
    a.setOutlineThickness(1);
    a.setOutlineColor(Color::Black);
    window.draw(a);
}

const int N = 20;

const char map[52][53] = {
".............##..................##....#...#........",
"......#......##.....#..#...................##..#....",
".......#.....##..#.#.......##.......................",
".........#########............#.................#...",
".####.#########.##..##....#....#...................#",
".#.###########.#.#............#.........#.#.....#..#",
"##.##############.#....##......................#....",
".########....#..#..........#........#...#.#....#....",
"........##..##....#..#..##.#.#............#.#.......",
"...#........##....#....#..#.....#.......##..........",
"............##..................#...#....#..........",
"............##....#..........#..##................#.",
"...........##..#................#..........#......#.",
"............###...#..#..##....#...........#.........",
"....#......######...........#...........###..#...##.",
"...........#####.#........#................#.......#",
"...........###...#...#...........#..................",
"........#..#..#..##........#....##.....##...#.#.....",
".........#...##..###............###.#.....#.........",
".....#...#....#.#...#........#..##..#...#......#....",
"..............####...#..#....####..........#........",
"..#.........#...###.......###.######.....#..........",
"..#......#.#...#.###.......#######...#.#............",
"........####......##..#.#.....####...........#..#.#.",
"...###...##.....#..#.........#.##....#...#...##.#...",
"................#..............##...................",
"..#...............#...#..#.#...###.....#............",
"...........#................#..###.........#......#.",
"..#..#.....................#.#.##...#.#.........#...",
"#.#......##..#................###.#........#...##...",
"..#..#....#...#.#............#####.....#..#....#....",
"..................#........######..........#........",
"................#.......#..###.....#...#..........#.",
"....#...........#....#.....##.......................",
"#...#.....#...............##..........##......#.....",
"......#.....#.#..........###..#..#....#...#........#",
".#......................###........#.#...#..........",
"........#..#..#..........##...###....#........#...#.",
".#.#....................#.#....#..........##.....#..",
".......#......#......#..........#...#.............#.",
".................#.#...........#.#..................",
"..#...............#..................#....##......##",
".....#.........#..............#......#.#..........##",
"..#.#########.#####...........#....#..##............",
"....####.##########...........#.##.....#.....#.....#",
"....................#.......##..##.....#....#.......",
".#...............................##...............##",
"..................#......#.......##...#...........#.",
".....................#.#.........##..#..............",
".#........#.#.##.#.#........#.....##............#...",
"..#..#................#......#..#.##.#..##...#......",
"....#.....#..#...#........#.....#..#...#...##......."};

const char alphabet[53] = "abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ";

string str_coords(int i, int j) {
    return alphabet[j] + to_string(52 - i);
}

int decode(char x) {
    if ('a' <= x && x <= 'z') {
        return x - 'a';
    } else {
        return 26 + x - 'A';
    }
}

double get_dist(string a, string b) {
    int di = decode(a[0]) - decode(b[0]);
    int dj = stoi(a.substr(1)) - stoi(b.substr(1));
    return hypot(di, dj);
}

set<pair<pair<int, int>, pair<int, int>>> edges;

bool ok(int i) {
    return 0 <= i && i < N;
}

void almost_sleep() {
    clock_t fn = clock() + CLOCKS_PER_SEC / 10;
    while (clock() < fn) {
        ;
    }
}

void iteration() {
    for (int i = 0; i < N; ++i) {
        for (int j = 0; j < N; ++j) {
            if (map[i][j] != '#') {
                continue;
            }
            draw_circle(50 + 16 * j, 50 + 16 * i, 6, Color::White);
        }
    }
    for (auto ppa : edges) {
        int a, b, c, d;
        tie(a, b) = ppa.first;
        tie(c, d) = ppa.second;
        draw_line(50 + 16 * b, 50 + 16 * a, 50 + 16 * d, 50 + 16 * c);
    }
    window.display();
    cerr << "First tap" << endl;
    while (!Mouse::isButtonPressed(Mouse::Left)) {
        ;
    }
    sleep(seconds(0.2));
    auto vec = sf::Mouse::getPosition(window);
    int b = (vec.x - 50 + 8) / 16;
    int a = (vec.y - 50 + 8) / 16;
    if (!ok(a) || !ok(b) || map[a][b] != '#') {
        return;
    }
    cerr << "Second tap" << endl;
    while (!Mouse::isButtonPressed(Mouse::Left)) {
        ;
    }
    sleep(seconds(0.5));
    vec = sf::Mouse::getPosition(window);
    int d = (vec.x - 50 + 8) / 16;
    int c = (vec.y - 50 + 8) / 16;
    window.display();
    if (!ok(c) || !ok(d) || map[c][d] != '#') {
        return;
    }
    if (a == c && b == d) {
        return;
    }
    cerr << "Xor: (" << a << ", " << b << ") -> (" << c << ", " << d << ")" << endl;
    pair<int, int> ab(a, b);
    pair<int, int> cd(c, d);
    if (ab > cd) {
        swap(ab, cd);
    }
    assert(ab < cd);
    pair<pair<int, int>, pair<int, int>> abcd(ab, cd);
    if (edges.count(abcd)) {
        edges.erase(abcd);
    } else {
        edges.insert(abcd);
    }
}

int main() {
    ContextSettings settings;
    settings.antialiasingLevel = 8;
    window.create(VideoMode(X, Y), "Main window", Style::Default, settings);

    int psize = 0;
    for (int i = 0; i < N; ++i) {
        for (int j = 0; j < N; ++j) {
            psize += map[i][j] == '#';
        }
    }

    while (window.isOpen()) {
        check_event();
        window.clear(Color::White);
        iteration();
        window.display();
        sleep(seconds(0.1));
        cout << edges.size() << " / " << psize - 1 << " edges" << endl;
        std_map<pair<int, int>, int> cnt;
        for (auto ppa : edges) {
            ++cnt[ppa.first];
            ++cnt[ppa.second];
        }
        pair<int, int> start(-1, -1);
        for (auto pa : cnt) {
            if (pa.second == 1) {
                start = pa.first;
            }
        }
        if (start.first == -1) {
            continue;
        }
        set<pair<int, int>> used    = {start};
        vector<string> path         = {str_coords(start.first, start.second)};

        while (1) {
            bool run = false;
            for (auto ppa : edges) {
                if (ppa.first != start || used.count(ppa.second)) {
                    swap(ppa.first, ppa.second);
                }
                if (ppa.first != start || used.count(ppa.second)) {
                    continue;
                }
                start = ppa.second;
                used.insert(start);
                path.push_back(str_coords(start.first, start.second));
                run = true;
            }
            if (!run) {
                break;
            }
        }
        if ((int)path.size() != psize) {
            cout << "Wrong len (" << path.size() << ")" << endl;
            continue;
        }
        cout << "Path:" << endl;
        double sum = 0;
        for (auto e : path) {
            cout << e << " ";
        }
        cout << endl;
        for (int i = 0; i + 1 < (int)path.size(); ++i) {
            sum += get_dist(path[i], path[i + 1]);
        }
        cout << "Sum = " << sum << endl;
    }

    return 0;
}