dlgshow.cpp

算法分析里的最近点对问题的实现

// DlgShow.cpp : implementation file
//

#include "stdafx.h"
#include "PairPoint.h"
#include "DlgShow.h"

#ifdef _DEBUG
#define new DEBUG_NEW
#undef THIS_FILE
static char THIS_FILE[] = __FILE__;
#endif

/////////////////////////////////////////////////////////////////////////////
// CDlgShow dialog


CDlgShow::CDlgShow(CWnd* pParent /*=NULL*/)
	: CDialog(CDlgShow::IDD, pParent)
{
	//{{AFX_DATA_INIT(CDlgShow)
		// NOTE: the ClassWizard will add member initialization here
	//}}AFX_DATA_INIT
}


void CDlgShow::DoDataExchange(CDataExchange* pDX)
{
	CDialog::DoDataExchange(pDX);
	//{{AFX_DATA_MAP(CDlgShow)
		// NOTE: the ClassWizard will add DDX and DDV calls here
	//}}AFX_DATA_MAP
}


BEGIN_MESSAGE_MAP(CDlgShow, CDialog)
	//{{AFX_MSG_MAP(CDlgShow)
	ON_WM_PAINT()
	//}}AFX_MSG_MAP
END_MESSAGE_MAP()

/////////////////////////////////////////////////////////////////////////////
// CDlgShow message handlers
//计算执行时间
static LARGE_INTEGER _tstart, _tend;
static LARGE_INTEGER freq;
void CDlgShow::tstart()
{
    static int first = 1;

    if(first) {
        QueryPerformanceFrequency(&freq);
        first = 0;
    }
    QueryPerformanceCounter(&_tstart);
}

void CDlgShow::tend()
{
    QueryPerformanceCounter(&_tend);
}

double CDlgShow::tval()
{
    return ((double)_tend.QuadPart -
                (double)_tstart.QuadPart)/((double)freq.QuadPart);
}

void CDlgShow::OnPaint() 
{
	CPaintDC dc(this); // device context for painting
	
	// TODO: Add your message handler code here
	CPen pen;
	pen.CreatePen(PS_SOLID,1,RGB(255,0,0));
	dc.SelectObject(&pen);

	if(m_flag != 3)  //一维情况
	{
		
		//画数轴
		CRect rc;
		this->GetClientRect(&rc);
		int x = rc.CenterPoint().x;
		int y = rc.CenterPoint().y;
		dc.MoveTo(x-200,y);
		dc.LineTo(x+200,y);
		dc.TextOut(x+200,y-8,">x");
		dc.TextOut(x-2,y-202,"^y");
		dc.MoveTo(x,y-200);
		dc.LineTo(x,y+200);
		
		//	pen.DeleteObject();
		//	pen.CreatePen(PS_SOLID,25,RGB(0,255,0));
		//	dc.SelectObject(&pen); 
		
		//产生随机点
		for (int i=1;i<=m_ywS[0];i++)
		{
			int temp = (rand()%400)+x-200;
			m_ywS[i] = temp;
			dc.Ellipse(temp-2,y-2,temp+2,y+2);
		}
		
		//找最近点对
		int res[2];
		res[0]=0;
		res[1]=0;
		CBrush BrushBlue; 
		BrushBlue.CreateSolidBrush(RGB(0,255,0)); 
		CBrush* pOldBrush; 
		pOldBrush = dc.SelectObject(&BrushBlue);
		
		int d;
		tstart();
		if (m_flag == 1)
		{
			OldMethod(m_ywS,res);
		}
		else if(m_flag == 0)
		{
			NewMethod(m_ywS,d,res);
		}
		dc.Ellipse(res[0]-2,y-2,res[0]+2,y+2);
		dc.Ellipse(res[1]-2,y-2,res[1]+2,y+2);
		tend();
		CString s;
		s.Format("算法执行时间是：%f",tval());
		dc.TextOut(10,10,s);
	}
	

	// Do not call CDialog::OnPaint() for painting messages
}

//传统方法
bool CDlgShow::OldMethod(int s[], int res[])
{
	int min = abs(s[1]-s[2]);
	for (int i=1; i<=s[0]; i++)
	{
		for (int j=i+1; j<=s[0]; j++)
		{
			if (abs(s[i]-s[j])<=min)
			{
				min = abs(s[i]-s[j]);
				res[0] = s[i];
				res[1] = s[j];
			}
		}
	}

	return true;
}

//分治技术
bool CDlgShow::NewMethod(int s[], int &d, int res[])
{
	//回归条件
	if (s[0]<2)
	{
		d = 65535;
		return false; //一个点没有距离
	}
	else if (s[0] == 2)
	{
		d = abs(s[1]-s[2]);
		res[0] = s[1];
		res[1] = s[2];
		return true;
	}
	//确定m
	int m = (QMax(s)+QMin(s))/2;
	//划分集合
	int s1[50+1],s2[50+1];
	int n1 = 0;
	int n2 = 0;
	for (int i=1;i<=s[0];i++)
	{
		if (s[i] < m)
		{
			s1[++n1] = s[i];
		}
		else
		{
			s2[++n2] = s[i];
		}
	}
	s1[0] = n1;	//数组第一个存储该集合的点个数
	s2[0] = n2;
	//分治
	int d1,d2;
	int res1[2],res2[2];
	NewMethod(s1,d1,res1);
	NewMethod(s2,d2,res2);
	//合并解
	d = QMin(d1,d2,QMin(s2)-QMax(s1));
	if (d!=d1&&d!=d2)
	{
		res[0] = QMax(s1);
		res[1] = QMin(s2);
	}
	else if(d == d1)
	{
		res[0] = res1[0];
		res[1] = res1[1];
	}
	else if(d == d2)
	{
		res[0] = res2[0];
		res[1] = res2[1];
	}
	
	return true;
}

void CDlgShow::SetPointNum(int num, int flag)
{
	m_ywS[0] = num;
	m_flag = flag;
}


int CDlgShow::QMax(int a[])
{
	int max = a[1];
	for (int i=2; i<=a[0]; i++) 
	{
		if (a[i]>max)
			max = a[i];
	}
	return max;
}


int CDlgShow::QMin(int a[])
{
	int min = a[1];
	for (int i=2; i<=a[0]; i++) 
	{
		if (a[i]<min)
			min = a[i];
	}
	return min;
}

int CDlgShow::QMin(int a, int b, int c)
{
	a = a<b?a:b;
	a = a<c?a:c;
	return a;
}