 /**//*
题意:给出一棵树,现在欲添加一条新边,使得从起点出发遍历所有点再回到起点总距离减少
加一条新边会形成一个环,设在原来没有环时遍历这一段的点再回来距离为2*x
现在加入环后,距离变为x+y,所以问题其实就是求x-y的最大值
n<=200,O(n^2)枚举加入的边即可
注意一条路之间不能有点
用floyd处理dist(a,b)
*/
#include<cstdio>
#include<cstring>
#include<cmath>

 inline int min(int a,int b) {return a<b?a:b;}
 inline int max(int a,int b) {return a>b?a:b;}

const int MAXN = 205;
const double eps = 1e-6;
const double DINF = 1e20;

int x[MAXN],y[MAXN];
double w[MAXN][MAXN];

int main()
  {
int N;
 while(~scanf("%d",&N)) {
for(int i=1;i<=N;i++)
scanf("%d%d",&x[i],&y[i]);
for(int i=0;i<=N;i++)
for(int j=0;j<=N;j++)
w[i][j]=DINF;
int a,b;
 for(int i=1;i<=N;i++) {
scanf("%d%d",&a,&b);
w[a][b]=w[b][a]=sqrt(0.0+(x[a]-x[b])*(x[a]-x[b])+(y[a]-y[b])*(y[a]-y[b]));
}
//floyd
for(int k=0;k<=N;k++)
for(int i=0;i<=N;i++)
if(w[i][k]+eps<DINF)
for(int j=0;j<=N;j++)
if(w[i][j]>w[i][k]+w[k][j])w[i][j]=w[i][k]+w[k][j];
double Max = 0;
for(int i=0;i<=N;i++)
 for(int j=i+1;j<=N;j++) {
bool ok = true;
//check whether online
for(int k=0;k<=N;k++)
if(k!=i&&k!=j&&(x[i]-x[k])*(y[j]-y[k])==(x[j]-x[k])*(y[i]-y[k])
&&x[k]<=max(x[i],x[j])&&x[k]>=min(x[i],x[j])&&y[k]<=max(y[i],y[j])&&y[k]>=min(y[i],y[j])
 ) {
ok=false;
break;
}
 if(ok) {
double tmp = w[i][j]-sqrt(0.0+(x[i]-x[j])*(x[i]-x[j])+(y[i]-y[j])*(y[i]-y[j]));
 if(tmp>Max+eps) {
Max=tmp;
a=i,b=j;
}
}
}
if(Max<eps)puts("-1");
else printf("%d %d\n",a,b);
}
return 0;
}
|
|
常用链接
随笔分类
Links
搜索
最新评论

|
|