求助 一直输出0
  • 板块P2632 Explorer
  • 楼主Lqwq
  • 当前回复0
  • 已保存回复0
  • 发布时间2021/10/10 18:13
  • 上次更新2023/11/4 04:08:50
查看原帖
求助 一直输出0
327069
Lqwq楼主2021/10/10 18:13
#include <iostream>
#include <cstdio>
#include <cmath>
#include <algorithm>
#include <cstring>
#include <string>
using namespace std;

//结构体存点 l1存n的点 l2存m的点 
struct lwt
{
	int x;//x坐标 
	int y;//y坐标 
}l1[100005],l2[100005];

double t[100005];//记录计算坐标的t
int n,m,tot,fa[100005],sum,cnt; 

//图 
struct lwwt
{
	int to;//起点 
	int from;//终点 
	double w;//权值 
}mapp[100005];

bool getin();//读入函数 
void build();//建立图 
double dist(double x,double y,double x1,double y1);
bool cmp(lwwt a,lwwt b)
{
	return a.w<b.w;
}
void klskr();
int find(int x);

int main()
{
	
	bool x=getin();
	if(x==false)
	{
		printf("0.000");
		return 0;
	}
	build();
	for(int i=1;i<=n+m;i++)
	fa[i]=i;
	klskr();
	
	return 0;
}

//计算坐标的函数 
double pos(int x,int y,double t)
{
	return (double)x*(1.0-t)+(double)y*(1.0-t);
}

//求两点之间距离的函数 
double dist(double x,double y,double x1,double y1)
{
	return sqrt((x-x1)*(x-x1)+(y-y1)*(y-y1));
}

//读入数据 
bool getin()
{
//	读入n和m有几个点 
	scanf("%d%d",&n,&m);
	
//	特判 
	if(n==0&&m==0)
	return false;
	
//	读入n常数 
	int xn,yn,xn1,yn1;
	scanf("%d%d%d%d",&xn,&yn,&xn1,&yn1);
//	读入t常数 
	for(int i=1;i<=n;i++)
	scanf("%lf",&t[i]);
//	为防止有重复的t,去重 
	sort(t+1,t+1+n);
	n=unique(t+1,t+1+n)-t;
//	计算坐标 
	for(int i=1;i<=n;i++)
	{
		l1[i].x=pos(xn,xn1,t[i]);
		l1[i].y=pos(yn,yn1,t[i]);
	}
	
//	读入m的 操作与n相同
	int xm,ym,xm1,ym1; 
	scanf("%d%d%d%d",&xm,&ym,&xm1,&ym1);
	memset(t,0.0,sizeof(t));
	for(int i=1;i<=m;i++)
	scanf("%lf",&t[i]);
	sort(t+1,t+1+m);
	m=unique(t+1,t+1+m)-t;
	for(int i=1;i<=m;i++)
	{
		l2[i].x=pos(xm,xm1,t[i]);
		l2[i].y=pos(ym,ym1,t[i]);
	}
	
	return true;
}

//建最小生成树的图 
void build()
{
//	建图 n上的 因为是一条直线 所以只用网后面建
	for(int i=1;i<n;i++)
	{
		mapp[++tot].from=i;
		mapp[tot].to=i+1;
		mapp[tot].w=dist(l1[i].x,l1[i].y,l1[i+1].x,l1[i+1].y);
	}
//	m同理 
	for(int i=1;i<m;i++)
	{
		mapp[++tot].from=i+n;
		mapp[tot].to=i+n+1;
		mapp[tot].w=dist(l2[i].x,l2[i].y,l2[i+1].x,l2[i+1].y);
	}
	
//	代码核心 n和m的点连起来 要是用(n+m)^2的大暴力会全部超时 
	for(int i=1;i<=n;i++)
	{
		int r=1,l=m;
		while(l+4<r)
		{
			int a=(r*2+l)/3;
			int b=(l*2+r)/3;
			if(dist(l2[a].x,l2[a].y,l1[i].x,l1[i].y)>dist(l2[b].x,l2[b].y,l1[i].x,l1[i].y))
			r=a;
			else
			l=b;
		}
		for(int j=r-1;j<=l+1;j++)
		{
			if(j>=1&&j<=m) 
			{
				mapp[++tot].from=i;
				mapp[tot].to=j+n;
				mapp[tot].w=dist(l1[i].x,l1[i].y,l2[j].x,l2[j].y);
			}
		}
	}
	
	for(int i=1;i<=m;i++)
	{
		int r=1,l=n;
		while(l+4<r)
		{
			int a=(r*2+l)/3;
			int b=(l*2+r)/3;
			if(dist(l1[a].x,l1[a].y,l2[i].x,l2[i].y)>dist(l1[b].x,l1[b].y,l2[i].x,l2[i].y))
			r=a;
			else
			l=b;
		}
		for(int j=r-1;j<=l+1;j++)
		{
			if(j>=1&&j<=n) 
			{
				mapp[++tot].from=i;
				mapp[tot].to=j+n;
				mapp[tot].w=dist(l1[j].x,l1[j].y,l2[i].x,l2[i].y);
			}
		}
	}
	
}

int find(int x)
{
	while(x!=fa[x])
	x=fa[x];
	return x;
}

void klskr()
{
	sort(mapp+1,mapp+1+tot,cmp);
	for(int i=1;i<=tot;i++)
	{
		int a=find(mapp[i].to);
		int b=find(mapp[i].from);
		if(a==b)
		continue;
		sum+=mapp[i].w;
		fa[a]=b;
		if(++cnt==n+m-1)
		break;
	}
	printf("%.3lf",sum);
}
2021/10/10 18:13
加载中...