#include <windows.h>
#include <time.h>
#include <math.h>

#define WINDOW_WIDTH  400
#define WINDOW_HEIGHT 420
#define MY_INTERVAL 50
#define NUMBER_OF_PIXEL 200

char* g_szApplicationName="旅行家问题（DP近似解）";
char* g_szWindowClassName="LinrenWindowClass";

POINT mypix[NUMBER_OF_PIXEL];
POINT myline[NUMBER_OF_PIXEL+1]={0};
int showpos=0;

inline int RandInt(int x,int y){
    return rand()%(y-x+1)+x;
}

void travel(int *a,int *path,int len){
    int *ta,*tb;
    int *p;
    int flg;
    int i,j,k,t;
    int x,y,z;
    ta=(int*)malloc(sizeof(int)*(len-1)*len);
    tb=(int*)malloc(sizeof(int)*(len-1)*len);
    memset(ta,0,sizeof(int)*(len-1)*len);
    memset(tb,0,sizeof(int)*(len-1)*len);
    memset(path,0,sizeof(int)*(len+1));

    for(k=1;k<len;k++){
        *(ta+len*(k-1))=*(a+k*len);
        *(ta+len*(k-1)+k)=1;
    }
    flg=1;
    for(z=2;z<len;z++){
        for(i=1;i<len;i++){
            y=-1;
            for(k=1;k<len;k++){
                if(flg==1){
                    if(*(ta+len*(k-1))==-1) continue;
                    if(*(ta+len*(k-1)+i)!=0) continue;
                    x=*(a+len*i+k)+*(ta+len*(k-1));
                }else{
                    if(*(tb+len*(k-1))==-1) continue;
                    if(*(tb+len*(k-1)+i)!=0) continue;
                    x=*(a+i*len+k)+*(tb+len*(k-1));
                }
                if(y==-1||x<y){
                    j=k;y=x;
                }
            }
            if(y==-1){
                if(flg==1) *(tb+len*(i-1))=y;
                else *(ta+len*(i-1))=y;
                continue;
            }
            if(flg==1){
                *(tb+len*(i-1))=y;
                for(k=1;k<len;k++){
                    if(*(ta+len*(j-1)+k)==0) *(tb+len*(i-1)+k)=0;
                    else *(tb+len*(i-1)+k)=*(ta+len*(j-1)+k)+1;
                }
                *(tb+len*(i-1)+i)=1;
            }else{
                *(ta+len*(i-1))=y;
                for(k=1;k<len;k++){
                    if(*(tb+len*(j-1)+k)==0) *(ta+len*(i-1)+k)=0;
                    else *(ta+len*(i-1)+k)=*(tb+len*(j-1)+k)+1;
                }
                *(ta+len*(i-1)+i)=1;
            }
        }
        if(flg==1) flg=0;
        else flg=1;
    }
    
    y=-1;
    for(i=1;i<len;i++){
        if(flg==1){
            if(*(ta+len*(i-1))==-1) continue;
            x=*(ta+len*(i-1))+*(a+i);
        }else{
            if(*(tb+len*(i-1))==-1) continue;
            x=*(tb+len*(i-1))+*(a+i);
        }
        if(y==-1||x<y){
            y=x;t=i;
        }
    }

    /**打印结果************************/
    if(flg==1) p=ta+len*(t-1);
    else p=tb+len*(t-1);
    path[0]=0;
    for(i=1;i<len;i++){
        path[p[i]]=i;
    }
    path[i]=0;
    /************************打印结果**/

    free(ta);free(tb);
}

void myfun(LPVOID sc){
    HWND* hwnd=(HWND*)sc;
    int i,j,*list,ds;
    double dis;
    int path[NUMBER_OF_PIXEL+1]={0};
    char str[1024]={0};
    list=(int*)malloc(sizeof(int)*NUMBER_OF_PIXEL*NUMBER_OF_PIXEL);
    memset(list,0,sizeof(int)*NUMBER_OF_PIXEL*NUMBER_OF_PIXEL);
    for(i=0;i<NUMBER_OF_PIXEL;i++){
        for(j=i+1;j<NUMBER_OF_PIXEL;j++){
            dis=sqrt((mypix[i].x-mypix[j].x)*(mypix[i].x-mypix[j].x)+(mypix[i].y-mypix[j].y)*(mypix[i].y-mypix[j].y));
            ds=(int)(1000*dis);
            *(list+i*NUMBER_OF_PIXEL+j)=ds;
            *(list+j*NUMBER_OF_PIXEL+i)=ds;
        }
    }

    travel(list,path,NUMBER_OF_PIXEL);
    for(i=0;i<NUMBER_OF_PIXEL+1;i++){
        myline[i].x=mypix[path[i]].x;
        myline[i].y=mypix[path[i]].y;
    }
    free(list);
    while(1){
        Sleep(MY_INTERVAL);
        showpos++;
        if(showpos>NUMBER_OF_PIXEL+3) break;
    }
}

LRESULT CALLBACK WindowProc(HWND hwnd,UINT msg,WPARAM wParam,LPARAM lParam){
    static int cxClient,cyClient;
    static HDC hdcBackBuffer;
    static HBITMAP hBitmap;
    static HBITMAP hOldBitmap;

    switch(msg){
    case WM_CREATE:
        {
            RECT rect;
            GetClientRect(hwnd,&rect);
            cxClient=rect.right;
            cyClient=rect.bottom;
            int i,x,y;
            srand((int)time(0));
            for(i=0;i<100;i++) RandInt(0,0);
            for(i=0;i<NUMBER_OF_PIXEL;i++){
                x=RandInt(20,380);y=RandInt(20,380);
                mypix[i].x=x;mypix[i].y=y;
                Ellipse(hdcBackBuffer,x-5,y-5,x+5,y+5);
            }
            for(i=0;i<NUMBER_OF_PIXEL;i++){
                SetPixel(hdcBackBuffer,mypix[i].x,mypix[i].y,NULL);
            }
            hdcBackBuffer=CreateCompatibleDC(NULL);
            HDC hdc=GetDC(hwnd);
            hBitmap=CreateCompatibleBitmap(hdc,cxClient,cyClient);
            hOldBitmap=(HBITMAP)SelectObject(hdcBackBuffer,hBitmap);
            ReleaseDC(hwnd,hdc);
        }
        break;

    case WM_PAINT:
        {
            PAINTSTRUCT ps;
            BeginPaint(hwnd,&ps);
            BitBlt(hdcBackBuffer,0,0,cxClient,cyClient,NULL,NULL,NULL,WHITENESS);
            int i,x,y;
            for(i=0;i<NUMBER_OF_PIXEL;i++){
                x=mypix[i].x;y=mypix[i].y;
                Ellipse(hdcBackBuffer,x-5,y-5,x+5,y+5);
            }
            for(i=0;i<NUMBER_OF_PIXEL&&i<showpos;i++){
                if(myline[i+1].x==0) break;
                MoveToEx(hdcBackBuffer,myline[i].x,myline[i].y,0);
                LineTo(hdcBackBuffer,myline[i+1].x,myline[i+1].y);
            }
            BitBlt(ps.hdc,0,0,cxClient,cyClient,hdcBackBuffer,0,0,SRCCOPY);
            EndPaint(hwnd,&ps);Sleep(10);
        }
        break;

    case WM_DESTROY:
        {
            SelectObject(hdcBackBuffer,hOldBitmap);
            DeleteDC(hdcBackBuffer);DeleteObject(hBitmap);
            PostQuitMessage(0);
        }break;
    }
    return DefWindowProc(hwnd,msg,wParam,lParam);
}

int WINAPI WinMain(HINSTANCE hInstance,HINSTANCE hPrevInstance,
                   LPSTR szCmdLine,int iCmdShow){
    HWND hWnd;
    WNDCLASSEX winclass;
    winclass.cbSize        = sizeof(WNDCLASSEX);
    winclass.style         = CS_HREDRAW | CS_VREDRAW;
    winclass.lpfnWndProc   = WindowProc;
    winclass.cbClsExtra    = 0;
    winclass.cbWndExtra    = 0;
    winclass.hInstance     = hInstance;
    winclass.hIcon         = LoadIcon(NULL, IDI_APPLICATION);
    winclass.hCursor       = LoadCursor(NULL, IDC_ARROW);
    winclass.hbrBackground = NULL;
    winclass.lpszMenuName  = NULL;
    winclass.lpszClassName = g_szWindowClassName;
    winclass.hIconSm       = LoadIcon(NULL, IDI_APPLICATION);

    if (!RegisterClassEx(&winclass)){
        MessageBox(NULL,"RegisterClassEx Error!","error",0);return 0;
    }
    
    hWnd=CreateWindowEx(NULL,
        g_szWindowClassName,
        g_szApplicationName,
        WS_OVERLAPPED|WS_VISIBLE|WS_CAPTION|WS_SYSMENU,
        GetSystemMetrics(SM_CXSCREEN)/2-WINDOW_WIDTH/2,
        GetSystemMetrics(SM_CYSCREEN)/2-WINDOW_HEIGHT/2,
        WINDOW_WIDTH,
        WINDOW_HEIGHT,
        NULL,NULL,hInstance,NULL);

    if(!hWnd){
        MessageBox(NULL,"CreateWindowEx Error!","error",0);
    }

    ShowWindow(hWnd, iCmdShow);UpdateWindow(hWnd);
    
    HANDLE thrd;
    thrd=CreateThread(NULL,0,(LPTHREAD_START_ROUTINE)myfun,(LPVOID)&hWnd,0,NULL);

    MSG msg;
    bool bDone=false;
    while(!bDone){
        while(PeekMessage(&msg,NULL,0,0,PM_REMOVE)){
            if(msg.message==WM_QUIT){
                TerminateThread(thrd,NULL);
                bDone=true;
            }else{
                TranslateMessage(&msg);DispatchMessage(&msg);
            }
        }
        InvalidateRect(hWnd,NULL,TRUE);UpdateWindow(hWnd);
    }
    UnregisterClass(g_szWindowClassName,winclass.hInstance);
    return msg.wParam;
}