3125844_ac_198ms_264k.c

北大大牛代码 1240道题的原代码 超级权威

#include <math.h>
#include <stdio.h>
#include <string.h>

int n;
double x[210], y[210], len[210];
int map[210][210], father[210];
int visited[210];

double dis(int a,int b)
{
	return sqrt((x[a]-x[b])*(x[a]-x[b])+(y[a]-y[b])*(y[a]-y[b]));
}

void dfs(int v,double length,int pa)
{
	int i;

	len[v] = length;
	visited[v] = 1;
	father[v] = pa;
	for(i = 0; i <= n; i++)
	{
		if(visited[i]==0&&map[v][i])
		{
			dfs(i,length+dis(i,v),v);
		}
	}
}

int lca(int a,int b)
{
	int mark[210];

	memset(mark,0,sizeof(mark));
	while(a!=-1)
	{
		mark[a] = 1;
		a = father[a];
	}
	while(b!=-1)
	{
		if(mark[b]==1)
			break;
		else
			b = father[b];
	}
	return b;
}

int main()
{
	int i, j, k, a, b, pa;
	double max, tmp;

	scanf("%d",&n);
	memset(map,0,sizeof(map));
	x[0] = y[0] = 0;
	for(i = 1; i <= n; i++)
	{
		scanf("%lf%lf",&x[i],&y[i]);
	}
	for(i = 1; i <= n; i++)
	{
		scanf("%d%d",&a,&b);
		map[a][b] = map[b][a] = 1;
	}
	memset(visited,0,sizeof(visited));
	dfs(0,0,-1);
	max = 0.0;
	for(i = 0; i <= n; i++)
	{
		for(j = i+1; j <= n; j++)
		{
			for(k = 0; k <= n; k++)
			{
				if(k!=i&&k!=j)
				{
					if((y[i]-y[j])*(x[i]-x[k])==(y[i]-y[k])*(x[i]-x[j])&&((x[i]<=x[k]&&x[k]<=x[j])||(x[j]<=x[k]&&x[k]<=x[i])))
					{
						break;
					}
				}
			}
			if(k==n+1)
			{
				pa = lca(i,j);
				tmp = len[i]+len[j]-2.0*len[pa]-dis(i,j);
				if(tmp > max)
				{
					max = tmp;
					a = i;
					b = j;
				}
			}
		}
	}
	if(max < 1e-8)
		puts("-1");
	else
		printf("%d %d\n",a,b);
	return 0;
}