3125100_wa.java

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

import java.util.*;

public class Main
{
	static class point
	{
		double x, y;
		point(double x, double y)
		{
			this.x = x;
			this.y = y;
		}
	}

	static final double INF = 100000000.0;
	static boolean [] visited = new boolean [300];
	static double [][] map = new double [300][300];
	static int n;
	static point [] p = new point [300];
	static int [] father = new int [300];
	static double [][] dis = new double [300][300];
	static boolean [][] Map = new boolean [300][300];

	private static void floyd()
	{
		int i, j, k;

		for(k = 0; k < n; k++)
		{
			for(i = 0; i < n; i++)
			{
				if(map[i][k]!=INF)
				{
					for(j = 0; j < n; j++)
					{
						if(map[i][k]+map[k][j]<map[i][j])
						{
							map[i][j] = map[i][k]+map[k][j];
						}
					}
				}
			}
		}
	}

	public static int getLCA(int a,int b)
	{
		boolean [] mark = new boolean [300];

		while(a!=-1)
		{
			mark[a] = true;
			a = father[a];
		}
		while(b!=-1)
		{
			if(mark[b])
				return b;
			else
				b = father[b];
		}
		return -1;
	}

	public static void dfs(int v,int pa)
	{
		int i;

		visited[v] = true;
		father[v] = pa;
		for(i = 0; i < n; i++)
		{
			if(v!=i&&!visited[i]&&Map[v][i])
			{
				dfs(i,v);
			}
		}
	}

	public static void main(String [] args)
	{
		Scanner cin = new Scanner (System.in);
		int i, j, k;
		int a, b;
		double tmp, x, y;

		n = cin.nextInt();
		p[0] = new point(0,0);
		for(i = 1; i <= n; i++)
		{
			x = cin.nextDouble();
			y = cin.nextDouble();
			p[i] = new point(x,y);
		}
		for(i = 0; i < n+1; i++)
		{
			map[i][i] = 0;
			dis[i][i] = 0;
			for(j = i+1; j < n+1; j++)
			{
				dis[i][j] = dis[j][i] = Math.hypot(p[i].x-p[j].x,p[i].y-p[j].y);
				map[i][j] = map[j][i] = INF;
			}
		}
		for(i = 0; i < n; i++)
		{
			a = cin.nextInt();
			b = cin.nextInt();
			map[a][b] = map[b][a] = dis[a][b];
			Map[a][b] = Map[b][a] = true;
		}
		n++;
		double max = 0.0;
		a = b = 0;
		dfs(0,-1);
		floyd();
		for(i = 0; i < n; i++)
		{
			for(j = i+1; j < n; j++)
			{
				if(Map[i][j])
				{
					continue;
				}
				boolean fail = false;
				for(k = 0; k < n; k++)
				{
					if(k!=i&&k!=j)
					{
						if((p[i].y-p[j].y)*(p[i].x-p[k].x)==(p[i].x-p[j].x)*(p[i].y-p[k].y))
						{
							fail = true;
							break;
						}
					}
				}
				if(!fail)
				{
					int d = getLCA(i,j);
					if(d == -1)
						while(true);
					tmp = map[d][i]+map[d][j]-dis[i][j];
					if(tmp > max)
					{
						max = tmp;
						a = i;
						b = j;
					}
				}
			}
		}
		if(max < 1e-8)
		{
			System.out.println("-1");
		}
		else
		{
			System.out.println(a+" "+b);
		}
	}
}