为啥 ABC 贪心法交过来不对
  • 板块UVA1411 Ants
  • 楼主DengDuck鄧德
  • 当前回复7
  • 已保存回复7
  • 发布时间2024/9/28 22:52
  • 上次更新2024/9/29 13:43:23
查看原帖
为啥 ABC 贪心法交过来不对
501947
DengDuck鄧德楼主2024/9/28 22:52
#include<bits/stdc++.h>
#define LL long long
#define LF long double
#define pLL pair<LL,LL>
#define X first
#define Y second
using namespace std;
const int N=305;
int n,P[N];
pLL A[N],B[N];
LF Dis(pLL A,pLL B){return sqrtl((A.X-B.X)*(A.X-B.X)+(A.Y-B.Y)*(A.Y-B.Y));}
int main()
{
	cin>>n;
	for(int i=1;i<=n;i++)P[i]=i;
	for(int i=1;i<=n;i++)cin>>A[i].X>>A[i].Y;
	for(int i=1;i<=n;i++)cin>>B[i].X>>B[i].Y;
	for(int T=1;T<=n;T++)
	{
		for(int i=1;i<=n;i++)
		for(int j=i+1;j<=n;j++)
		{
			if(Dis(A[i],B[P[i]])+Dis(A[j],B[P[j]])>Dis(A[i],B[P[j]])+Dis(A[j],B[P[i]]))swap(P[i],P[j]);
		}
	}
	for(int i=1;i<=n;i++)printf("%d\n",P[i]);
}
2024/9/28 22:52
加载中...