курсач

// Win32Project1.cpp: определяет точку входа для приложения.
//

#include "stdafx.h"
#include "Win32Project1.h"
#include <stdio.h>
#include <Math.h>


#define MAX_LOADSTRING 100

// Глобальные переменные:
HINSTANCE hInst;                                // текущий экземпляр
TCHAR szTitle[MAX_LOADSTRING];                  // Текст строки заголовка
TCHAR szWindowClass[MAX_LOADSTRING];            // имя класса главного окна

// Отправить объявления функций, включенных в этот модуль кода:
ATOM                MyRegisterClass(HINSTANCE hInstance);
BOOL                InitInstance(HINSTANCE, int);
LRESULT CALLBACK    WndProc(HWND, UINT, WPARAM, LPARAM);
INT_PTR CALLBACK    About(HWND, UINT, WPARAM, LPARAM);

int APIENTRY _tWinMain(_In_ HINSTANCE hInstance,
                     _In_opt_ HINSTANCE hPrevInstance,
                     _In_ LPTSTR    lpCmdLine,
                     _In_ int       nCmdShow)
{
    UNREFERENCED_PARAMETER(hPrevInstance);
    UNREFERENCED_PARAMETER(lpCmdLine);

    // TODO: разместите код здесь.
    MSG msg;

    // Инициализация глобальных строк
    LoadString(hInstance, IDS_APP_TITLE, szTitle, MAX_LOADSTRING);
    LoadString(hInstance, IDC_WIN32PROJECT1, szWindowClass, MAX_LOADSTRING);
    MyRegisterClass(hInstance);

    // Выполнить инициализацию приложения:
    if (!InitInstance (hInstance, nCmdShow))
    {
        return FALSE;
    }


    // Цикл основного сообщения:
    while (GetMessage(&msg, NULL, 0, 0))
    {
            TranslateMessage(&msg);
            DispatchMessage(&msg);
    }

    return (int) msg.wParam;
}

//
//  ФУНКЦИЯ: MyRegisterClass()
//
//  НАЗНАЧЕНИЕ: регистрирует класс окна.
//
ATOM MyRegisterClass(HINSTANCE hInstance)
{
    WNDCLASSEX wcex;

    wcex.cbSize = sizeof(WNDCLASSEX);

    wcex.style          = CS_HREDRAW | CS_VREDRAW;
    wcex.lpfnWndProc    = WndProc;
    wcex.cbClsExtra     = 0;
    wcex.cbWndExtra     = 0;
    wcex.hInstance      = hInstance;
    wcex.hIcon          = NULL;
    wcex.hCursor        = LoadCursor(NULL, IDC_ARROW);
    wcex.hbrBackground = (HBRUSH)(COLOR_BACKGROUND + 13);
    wcex.lpszMenuName   = NULL;
    wcex.lpszClassName  = szWindowClass;
    wcex.hIconSm        = NULL;

    return RegisterClassEx(&wcex);
}

//
//   ФУНКЦИЯ: InitInstance(HINSTANCE, int)
//
//   НАЗНАЧЕНИЕ: сохраняет обработку экземпляра и создает главное окно.
//
//   КОММЕНТАРИИ:
//
//        В данной функции дескриптор экземпляра сохраняется в глобальной переменной, а также
//        создается и выводится на экран главное окно программы.
//
BOOL InitInstance(HINSTANCE hInstance, int nCmdShow)
{
   HWND hWnd;

   hInst = hInstance; // Сохранить дескриптор экземпляра в глобальной переменной

   hWnd = CreateWindow(szWindowClass, szTitle, WS_OVERLAPPEDWINDOW,
      CW_USEDEFAULT, 0, CW_USEDEFAULT, 0, NULL, NULL, hInstance, NULL);

   //HWND button = CreateWindowW(L"BUTTON", L"Сбросить", WS_CHILD | WS_VISIBLE | BS_DEFPUSHBUTTON, 1300, 650, 100, 35, hWnd, (HMENU)101, (HINSTANCE)GetWindowLong(hWnd, GWL_HINSTANCE), NULL);

   if (!hWnd)
   {
      return FALSE;
   }

   ShowWindow(hWnd, nCmdShow);
   UpdateWindow(hWnd);

   return TRUE;
}

//
//  ФУНКЦИЯ: WndProc(HWND, UINT, WPARAM, LPARAM)
//
//  НАЗНАЧЕНИЕ:  обрабатывает сообщения в главном окне.
//
//  WM_COMMAND  - обработка меню приложения
//  WM_PAINT    -Закрасить главное окно
//  WM_DESTROY   - ввести сообщение о выходе и вернуться.
//
//

const int numEdges = 10;  //максимальное количество вершин острова
const int numIslands = 10;  //максимальное количество островов

//количество пользовательских островов
//int userIsland = 2;

int count = 0;
int countEnteredEdges = 0;
//матрица координат вершин
float islands[numIslands][numEdges][2] = {};
//матрица расстояний до островов
float M[numIslands][numIslands] = {};
//матрица координат мостов
float A[numIslands][numIslands][4] = {};
//покрывающее дерево
int tabu[numIslands][2] = {};

//дистанция от точки 1 до точки 2
float Distance(float x1, float y1, float x2, float y2)
{
    return sqrtf((x2 - x1)*(x2 - x1) + (y2 - y1)*(y2 - y1));
}
//записывает координаты в матрицу координат вершин островов
void WriteCoord(float x, float y) {
    for (int i = 0; i < numEdges; i++)
    {
        if (islands[count][i][0] <= 0 || islands[count][i][1] <= 0) {
            islands[count][i][0] = x;
            islands[count][i][1] = y;
            break;
        }
    }
}
//проверка на наличие в табу
int HasInTabu(int tabu[][2], int start, int end)
{
    for (int i = 0; i < numIslands; i++)
    {
        if (tabu[i][0] == start && tabu[i][1] == end)
            return 1;
    }
    return 0;
}

int TheEnd(int *G, int count)
{
    for (int i = 0; i < count-1; i++)
    {
        if (G[i + 1] != G[i])
            return 0;
    }
    return 1;
}
//округление???
float round(float value){
    return float(int(value*10000))/10000;
}

//возвращает 1, если есть точка пересечения перпендикуляра и прямой
int Point(float x1, float y1, float x2, float y2, float x0, float y0, float *x, float *y) {
    float a1, a2, b1, b2, c1, c2;
    a1 = y1 - y2; //x
    b1 = x2 - x1;    //y
    c1 = x1 * y2 - x2 * y1;

    a2 = b1;
    b2 = -a1;
    c2 = -(a2 * x0 + b2 * y0);
    float xp, yp;

    xp = -((c1 * b2 - c2 * b1) / (a1 * b2 - a2 * b1));
    yp = -((a1 * c2 - a2 * c1) / (a1 * b2 - a2 * b1));
    *x = xp;
    *y = yp;
    //вот тут что то не то
    if ((xp >= min(x1, x2) && xp <= max(x1, x2) && yp >= min(y1, y2) && yp <= max(y1, y2)))
        return round((xp - x1) / (x2 - x1)) == round((yp - y1) / (y2 - y1));
    else
        return 0;
}

void Reset()
{
    count = 0;
    countEnteredEdges = 0;

    for (int i = 0; i < numIslands; i++)
    {
        for (int j = 0; j < numIslands; j++)
        {
            A[i][j][0] = 0;
            A[i][j][1] = 0;
            A[i][j][2] = 0;
            A[i][j][3] = 0;
        }
    }

    for (int i = 0; i < numIslands; i++)
    {
        for (int j = 0; j < numIslands; j++)
        {
            M[i][j] = 0;
        }
    }

    for (int i = 0; i < numIslands; i++)
    {
        for (int j = 0; j < numEdges; j++)
        {
            islands[i][j][0] = 0;
            islands[i][j][1] = 0;
        }
    }

    for (int i = 0; i < numIslands; i++)
    {
        tabu[i][0] = 0;
        tabu[i][1] = 0;
    }

}

LRESULT CALLBACK WndProc(HWND hWnd, UINT message, WPARAM wParam, LPARAM lParam)
{
    int wmId, wmEvent;
    PAINTSTRUCT ps;
    HDC hdc;

    switch (message)
    {
    case WM_LBUTTONDOWN:
    {
        float xPos = LOWORD(lParam);
        float yPos = HIWORD(lParam);
        HPEN hpen = CreatePen(PS_SOLID, 2, RGB(255, 0, 0));
        HDC hdc = GetDC(hWnd);
        SelectObject(hdc, hpen);
        MoveToEx(hdc, xPos - 3, yPos - 3, NULL);
        LineTo(hdc, xPos + 3, yPos + 3);
        MoveToEx(hdc, xPos + 3, yPos - 3, NULL);
        LineTo(hdc, xPos - 3, yPos + 3);
        DeleteObject(hpen);
        WriteCoord(xPos, yPos);
        countEnteredEdges++;
        break;
    }
    case WM_KEYDOWN:
    {
        HDC hdc = GetDC(hWnd);
        int code = HIWORD(lParam) % 255 - 1;

        HPEN hpen = CreatePen(PS_SOLID, 2, RGB(255, 228, 49));
        SelectObject(hdc, hpen);
        SetTextColor(hdc, RGB(255, 255, 255));//Устанавливаем цвет текст
        SetBkColor(hdc, RGB(51, 153, 255));//Устанавливаем цвет бэкграунда
        if(code == 27 || code == 28){
            if (countEnteredEdges > 0)
            {
                int x = islands[count][0][0], y = islands[count][0][1];
                for (int i = 0; i < numEdges - 1; i++)
                {
                    if (islands[count][i + 1][0] <= 0 && islands[count][i + 1][1] <= 0)
                    {
                        MoveToEx(hdc, islands[count][i][0], islands[count][i][1], NULL);
                        LineTo(hdc, islands[count][0][0], islands[count][0][1]);
                        x = (x + islands[count][1][0]) / 2;
                        y = (y + islands[count][1][1]) / 2;
                        break;
                    }
                    MoveToEx(hdc, islands[count][i][0], islands[count][i][1], NULL);
                    LineTo(hdc, islands[count][i + 1][0], islands[count][i + 1][1]);
                    x = (x + islands[count][i+1][0]) / 2;
                    y = (y + islands[count][i+1][1]) / 2;
                }

                HBRUSH hBrush = CreateSolidBrush(RGB(240, 219, 125));
                SelectObject(hdc, hBrush);
                FloodFill(hdc, x, y, RGB(255, 228, 49));
                DeleteObject(hBrush);

                countEnteredEdges = 0;
                count++;
            }
            else
            {
                int min_i = 0;
                int min_j = 0;
                int isP = 0;
                float minDistance;

                //здесь перпендикуляры найти
                for (int i = 0; i < count; i++)
                {
                    int k = 0;

                    for (; k < count; k++)
                    {
                        if (k == i)
                            continue;

                        minDistance = Distance(islands[i][0][0], islands[i][0][1], islands[k][0][0], islands[k][0][1]);

                        for(int m = 0; m < numEdges; m++)
                        {
                            for(int j = 1; j < numEdges; j++)
                            {
                                if(islands[k][m][0] && islands[k][m][1] && islands[i][j][0] && islands[i][j][1])
                                {
                                    float temp = Distance(islands[k][m][0], islands[k][m][1], islands[i][j][0], islands[i][j][1]);

                                    if(temp < minDistance)
                                    {
                                        minDistance = temp;
                                        min_j = m;
                                        min_i = j;
                                    }
                                }
                            }
                        }

                        //тут идет проверка на перпендикуляры
                        float x, y;   //точка пересечения прямых
                        float xp, yp;
                        //что-то с матешой не так


                        for(int m = 0; m < numEdges; m++)
                        {
                            for(int j = 0; j < numEdges; j++)
                            {
                                if(islands[k][m][0] && islands[k][m][1])
                                {
                                    if (islands[i][j + 1][0] && islands[i][j + 1][1])
                                    {
                                        if (Point(islands[i][j][0], islands[i][j][1], islands[i][j + 1][0], islands[i][j + 1][1], islands[k][m][0], islands[k][m][1], &x, &y))
                                        {
                                            float temp = Distance(x, y, islands[k][m][0], islands[k][m][1]);
                                            if (temp < minDistance)
                                            {
                                                minDistance = temp;
                                                isP = 1;
                                                xp = x;
                                                yp = y;
                                                min_j = m;
                                            }
                                        }
                                    }
                                    else
                                    {
                                        //проверяем первый и последний
                                        if (Point(islands[i][0][0], islands[i][0][1], islands[i][j][0], islands[i][j][1], islands[k][m][0], islands[k][m][1], &x, &y))
                                        {
                                            float temp = Distance(x, y, islands[k][m][0], islands[k][m][1]);
                                            if (temp < minDistance)
                                            {
                                                minDistance = temp;
                                                isP = 1;
                                                xp = x;
                                                yp = y;
                                                min_j = m;
                                            }
                                        }
                                        break;
                                    }
                                }
                            }
                        }

                        M[i][k] = minDistance;
                        A[i][k][2] = islands[k][min_j][0];
                        A[i][k][3] = islands[k][min_j][1];

                        M[i][k] = minDistance;
                        A[i][k][2] = islands[k][min_j][0];
                        A[i][k][3] = islands[k][min_j][1];
                        if (isP)//если есть перпендикуляр
                        {

                            A[i][k][0] = xp;
                            A[i][k][1] = yp;
                        }
                        else
                        {
                            //сделать как М
                            A[i][k][0] = islands[i][min_i][0];
                            A[i][k][1] = islands[i][min_i][1];
                        }
                        isP = 0;
                        min_i = 0;
                        min_j = 0;
                    }
                }
                //находим покрывающее дерево
                //массив компонент связностей
                int G[numIslands] = {};
                //назначаем каждой вершине свою компоненту связности
                for (int i = 0; i < count; i++)
                    G[i] = i;

                //почему то появляется цикл при каких либо тестах

                int n = 0;
                int a = 0;
                int b = 0;
                //int max = count * (count - 1) / 2; //максимальное количество ребер в полном графе
                float min = 0;

                int max = count - 1;
                while (n < max)
                {
                    //находим минимальное ребро для сравнения
                    for (int i = 0; i < count; i++)
                    {
                        for (int j = 0; j < count; j++)
                        {
                            if (M[i][j] > 0 && !HasInTabu(tabu, i, j))
                            {
                                min = M[i][j];
                                a = i;
                                b = j;
                                break;
                            }
                        }
                        if(min)
                            break;
                    }

                    for (int i = 0; i < count; i++)
                    {
                        for (int j = 0; j < count; j++)
                        {
                            if (M[i][j] > 0 && !HasInTabu(tabu, i, j) && M[i][j] < min)
                            {
                                min = M[i][j];
                                a = i;
                                b = j;
                            }
                        }
                    }

                    //если в разных компонентах связности
                    if (G[a] != G[b])
                    {
                        int temp = G[b];
                        for (int i = 0; i < count; i++)
                            if (G[i] == temp) G[i] = G[a];

                        tabu[n][0] = a;
                        tabu[n][1] = b;
                        n++;
                    }
                    else
                    {
                        M[a][b] = 0;
                        M[b][a] = 0;
                    }

                    //нашли минимальное, тогда если существует путь в обратную, то он нам не нужен => обнуляем

                    if(M[a][b] > 0 && M[b][a] > 0)
                    {
                        if(M[a][b] < M[b][a])
                            M[b][a] = 0;
                        else
                            M[a][b] = 0;
                    }

                    if (TheEnd(G, count))
                        break;
                }
                int sum = 0;
                //нужен ли массив А или можно без него как то обойтись?
                SetTextColor(hdc, RGB(255,255,255));//Устанавливаем цвет текст
                SetBkColor(hdc, RGB(51,153,255));//Устанавливаем цвет бэкграунда
                for (int i = 0; i < count; i++)
                {
                    float x1, x2, y1, y2;
                    x1 = A[tabu[i][0]][tabu[i][1]][0];
                    y1 = A[tabu[i][0]][tabu[i][1]][1];
                    x2 = A[tabu[i][0]][tabu[i][1]][2];
                    y2 = A[tabu[i][0]][tabu[i][1]][3];
                    MoveToEx(hdc, x1, y1, NULL);
                    LineTo(hdc, x2, y2);
                    //TextOut(hdc, 50, 150, L"1," ,3);
                    DeleteObject(hpen);

                    int dist = Distance(x1, y1, x2, y2);
                    char distance[20];
                    _itoa_s(dist, distance, 10);
                    wchar_t temp[20];
                    mbstowcs(temp, distance, 5);
                    sum += dist;
                    TextOut(hdc, (x2 + x1) / 2, (y1 + y2) / 2, temp, strlen(distance));
                }
                char num[10];
                _itoa_s(sum, num, 10);
                char text[30] = "Summa: ";
                strcat_s(text, num);
                wchar_t temp[255];
                mbstowcs(temp, text, 30);

                TextOut(hdc, 5, 500, temp, strlen(text));

                break;
            }
        }
        if(code == 18)
        {
            HDC hdc = GetDC(hWnd);
                HBRUSH hBrush = CreateSolidBrush(RGB(51, 153, 255));
                SelectObject(hdc, hBrush);
                Reset();
                FloodFill(hdc, 0, 0, RGB(0, 0, 0));
                DeleteObject(hBrush);
        }
    }

    case WM_PAINT:
        hdc = BeginPaint(hWnd, &ps);
        // TODO: добавьте любой код отрисовки...

        TextOut(hdc, 5, 700, L"Нажмите R для сброса значений", 29);
        //SetTextColor(hdc, COLOR_GRAYTEXT + 4);
        EndPaint(hWnd, &ps);
        break;
/*
    case WM_COMMAND:
    {
        switch (LOWORD(wParam))
        {
            case 101:
            {
                HDC hdc = GetDC(hWnd);
                HBRUSH hBrush = CreateSolidBrush(RGB(51, 153, 255));
                SelectObject(hdc, hBrush);
                Reset();
                FloodFill(hdc, 0, 0, RGB(0, 0, 0));
                DeleteObject(hBrush);
            }
        }
        break;
    }
    */
    case WM_DESTROY:
        PostQuitMessage(0);
        break;
    default:
        return DefWindowProc(hWnd, message, wParam, lParam);
    }
    return 0;
}