2.cpp

这是一道大学生信息学奥林匹克竞赛的试题的解答

/*---------------------------------------
   2.C -- 孙永胜 line Demo
               (c), 2004
  ---------------------------------------*/

#include <windows.h>
#include <math.h>
///
int a[10000000],b[5000000],c[5000000];
int dd[2000000];int len;
long int tt[23];
	int n,m;
	int countnum(int);
	void drawpicture(HDC ,HWND,int);
	void count1(int,int,int,int);
	void count2(int,int);
	void count3(int);
	void drawatom(int,HDC,HWND ,int);
        void Drawline (HDC,HWND,int) ;
//////
LRESULT CALLBACK WndProc (HWND, UINT, WPARAM, LPARAM) ;
 //void Drawline (HDC,H) ;
int WINAPI WinMain (HINSTANCE hInstance, HINSTANCE hPrevInstance,
                    PSTR szCmdLine, int iCmdShow)
{
     static TCHAR szAppName[] = TEXT ("Bezier") ;
     HWND         hwnd ;
     MSG          msg ;
     WNDCLASS     wndclass ;
     
     wndclass.style         = CS_HREDRAW | CS_VREDRAW ;
     wndclass.lpfnWndProc   = WndProc ;
     wndclass.cbClsExtra    = 0 ;
     wndclass.cbWndExtra    = 0 ;
     wndclass.hInstance     = hInstance ;
     wndclass.hIcon         = LoadIcon (NULL, IDI_APPLICATION) ;
     wndclass.hCursor       = LoadCursor (NULL, IDC_ARROW) ;
     wndclass.hbrBackground = (HBRUSH) GetStockObject (WHITE_BRUSH) ;
     wndclass.lpszMenuName  = NULL ;
     wndclass.lpszClassName = szAppName ;
        
     if (!RegisterClass (&wndclass))
     {
          MessageBox (NULL, TEXT ("Program requires Windows NT/2000!"), 
                      szAppName, MB_ICONERROR) ;
          return 0 ;
     }
     
     hwnd = CreateWindow (szAppName, TEXT (" *折纸线* design by sys "),
                          WS_OVERLAPPEDWINDOW,
                          CW_USEDEFAULT, CW_USEDEFAULT,
                          CW_USEDEFAULT, CW_USEDEFAULT,
                          NULL, NULL, hInstance, NULL) ;
     
     ShowWindow (hwnd, iCmdShow) ;
     UpdateWindow (hwnd) ;
     
     while (GetMessage (&msg, NULL, 0, 0))
     {
          TranslateMessage (&msg) ;
          DispatchMessage (&msg) ;
     }
     return msg.wParam ;
}

LRESULT CALLBACK WndProc (HWND hwnd, UINT message, WPARAM wParam, LPARAM lParam)
{
     static POINT apt[4] ;static int rr=1;
     HDC          hdc ;
     PAINTSTRUCT  ps ;
     switch (message)
     {
     case WM_SIZE:
          return 0 ;

     case WM_LBUTTONDOWN:
     case WM_RBUTTONDOWN:
     case WM_MOUSEMOVE:
          if (wParam & MK_LBUTTON || wParam & MK_RBUTTON)
          {
               hdc = GetDC (hwnd) ;
          }
          SelectObject (hdc, GetStockObject (BLACK_PEN)) ;
          ReleaseDC (hwnd, hdc) ;
          return 0 ;
          
     case WM_PAINT:
          InvalidateRect (hwnd, NULL, TRUE) ;
          hdc = BeginPaint (hwnd, &ps) ;
          Drawline ( hdc, hwnd,rr++);
		  drawpicture(hdc,hwnd,0);//第三个参数显示方向序列的标志
          EndPaint (hwnd, &ps) ;
          return 0 ;
          
     case WM_DESTROY:
          PostQuitMessage (0) ;
          return 0 ;
     }
     return DefWindowProc (hwnd, message, wParam, lParam) ;
}

void  Drawline (HDC hdc,HWND hwnd,int xxx) 
{
	int i;	
 	n=xxx;m=countnum(n);//////////////////////////////////////////////                              ////////n
    len=40/xxx;
	for( i=0;i<m;i++)
		dd[i]=c[i]=0;
	count1(0,m,n,1);
	count2(n,m);
	count3(n);
    return;
}
int countnum(int n) 
{
	int i,j, sum=0;int temp=0;
	tt[0]=0;
	for( i=1;i<=n;i++)
	{	
		temp=1;
		for(j=i;j>1;j--)
		temp*=2;
		sum+=temp;
	    tt[i]=sum;
	}
	if (n<=0) sum=0;
	return sum;
}
void  count1(int i,int m,int n, int flage)
{
	static int j;
	if(flage) j=0;
	if(n>0)
	{a[j++]=(m+i)/2;a[j++]=n;
	count1(i,(m+i)/2,n-1,0);
	count1((m+i)/2,m,n-1,0);
	}
	else return;
}
void count2(int n,int m)
{
	int j,i,k=0;
	for( i=n;i>0;i--)
	{
		for( j=0;j<m;j++)
		{
			if(a[j*2+1]==i)
			   b[k++]=a[j*2];
		}
	}
}
void  count3(int n)
{
	int h,i,j;
    for (h=1;h<=n;h++) 
	{	
		for(i=tt[h]-1;i>tt[h-1]-1;i--)    //tt表用于优化速度
     // for(i=countnum(h)-1;i>countnum(h-1)-1;i--)
		{   
			int sum=0;
			for(j=0;j<b[i];j++)
				sum+=dd[j]; 
			if(sum%2)                      //ji shu ou shu
			    c[b[i]]= 65;
			else                           //因地跪顺序的不确定导致次拴法破产
                c[b[i]]= 67;
		}
    	for(i=tt[h]-1;i>tt[h-1]-1;i--)
	//	for(i=countnum(h)-1;i>countnum(h-1)-1;i--)
		{
			dd[b[i]]=c[b[i]];
		}
	}
}
void  drawpicture(HDC hdc,HWND hwnd,int flag)
{ 
	char s[10000];
	static int ff=0;
	RECT rect;
	GetClientRect(hwnd,&rect);
	int i;
//	int t1,t2,t3,t4;
	long int direction=0;	
//t1=t2=t3=t4=32767;
    drawatom(direction,hdc,hwnd,1);
	if(flag)
	{
	for(i=0;i<m;i++)
	{
	   s[i]=(char)c[i];
	}
	s[i]='\0';
    DrawText(hdc,TEXT(s),-1,&rect,DT_SINGLELINE|DT_CENTER|DT_VCENTER);
	}
	for( i=0;i<m;i++)
	{
		 if(c[i]==65)
			 direction--;
		 else
             direction++;
		   	drawatom(direction%4,hdc,hwnd,0);
	}
}
void  drawatom(int direction,HDC hdc ,HWND hwnd,int f)
{   
	static int x,y; 
	if(f)
	{x=400;y=200;}////////////////////////////////////////////////////////                      ///////x0,y0
   // int	len=6;///////////////////////////////////////////////////////                            //////len      	
	MoveToEx (hdc, x, y, NULL) ;  
	switch (direction)
	{
	case 0:
	     LineTo  (hdc, x+=len,y) ;
      	  break;
	case 1:
	     LineTo   (hdc, x,y+=len) ;
     	  break;
	case 2:
	     LineTo   (hdc, x-=len, y) ;
       	  break;
	case 3:
	     LineTo   (hdc, x,y-=len) ;
      	  break;
	}

	return;
}