#include "math.h"
#include <iostream>
using namespace std;
double length(int x1, int y1,int x2,int y2);
bool find(int u);
int Xn[100], Yn[100], Xm[100], Ym[100], N, M, graph[100][100], i, j, matchx[100], matchy[100], vis[100];
int main()
{

		cin >> N >> M;
		memset(graph, 0, sizeof(graph));
		for (i = 0; i < N; i++)
		{
			cin >> Xn[i] >> Yn[i];
		}
		for (i = 0; i < M; i++)
		{
			cin >> Xm[i] >> Ym[i];
		}
		for (i = 0; i < N - 1; i++)
		{
			double temp = length(Xn[i], Yn[i], Xn[i + 1], Yn[i + 1]);
			for (j = 0; j < M; j++)
			{
				double temp2 = length(Xn[i], Yn[i], Xm[j], Ym[j]) + length(Xn[i + 1], Yn[i + 1], Xm[j], Ym[j]);
				if (temp2 <= temp * 2)
				{
					graph[i][j] = 1;
				}
			}
		}
		memset(matchx, -1, sizeof(matchx));
		memset(matchy, -1, sizeof(matchy));
		int matchnumber=0;
		for (i = 0; i < N-1; i++)
		{
			memset(vis, 0, sizeof(vis));
			if (find(i))
			{
				matchnumber++;
			}
		}
		cout << matchnumber + N<<"\n";
		for (i = 0; i < N - 1; i++)
		{
			if (matchx[i] == -1)
			{
				cout << Xn[i] << " " << Yn[i] << " ";
			}
			else{
				cout << Xn[i] << " " << Yn[i] << " " << Xm[matchx[i]] << " " << Ym[matchx[i]] << " ";
			}
		}
		cout << Xn[N - 1] << " " << Yn[N - 1];

	return 0;
}
double length(int x1, int y1, int x2, int y2)
{
	return pow(pow((double)(x1 - x2), 2) + pow((double)(y1 - y2), 2), 0.5);
}
bool find(int u)
{
	int v;
	for (v = 0; v < M; v++)
	{
		if (graph[u][v] == 1 && vis[v] == 0)
		{
			vis[v] = 1;
			if (matchy[v] == -1 || find(matchy[v]))
			{
				matchy[v] = u;
				matchx[u] = v;
				return true;
			}
		}
	}
	return false;
}

• Re:79ms 332k附代码 (1835) 14111206046 2016-05-31 13:08:21