调了四个小时了!为啥零分?
  • 板块P2632 Explorer
  • 楼主pengze36
  • 当前回复0
  • 已保存回复0
  • 发布时间2023/12/15 21:30
  • 上次更新2023/12/16 08:33:45
查看原帖
调了四个小时了!为啥零分?
925491
pengze36楼主2023/12/15 21:30

求助!我的代码:

#include<iostream>
#include<cstdio>
#include<queue>
#include<cmath>
#include<algorithm>
#define ll int  
using namespace std;
struct ed{
	ll u,v;
	double d;
};
bool cmp(ed a,ed b){
	return a.d<b.d;
}
ll n,m;
double a1[200005],a2[200005];
double dis(double ax,double ay,double bx,double by){
	return sqrt((ax-bx)*(ax-bx)+(ay-by)*(ay-by));
}
ll f[200005];
ll find(ll x){
	if(f[x]==x) return x;
	return f[x]=find(f[x]);
}
ed e[600000];
int main(){
	scanf("%d%d",&n,&m);
	for(int i=1;i<=n+m;++i) f[i]=i;
	double ax,ay,bx,by;
	double cx,cy,dx,dy;
	scanf("%lf%lf%lf%lf",&ax,&ay,&bx,&by);
	scanf("%lf%lf%lf%lf",&cx,&cy,&dx,&dy);
	double k1=/*((by-ay==0)||(bx-ax)==0)?0:*/(by-ay)/(bx-ax);
	double b1=ay-k1*ax;
	double k2=/*(((dy-cy)==0)||(dx-cx==0))?0:*/(dy-cy)/(dx-cx);
	double b2=cy-k2*cx;
	double t;
	for(int i=1;i<=n;++i){
		scanf("%lf",&t);
		a1[i]=ax*t+bx*(1-t);
     	 }
	for(int i=1;i<=m;++i){
		scanf("%lf",&t);
		a2[i]=cx*t+dx*(1-t);
	}
	sort(a1+1,a1+1+n);
	sort(a2+1,a2+m+1);
	ll tot=0;
	for(int i=1;i<=m;++i){
	double  x=a2[i];
		double y=x*k2+b2;
		double k=-k1;
		double  b=y-k*x;
		double  nx=/*((b-b1)==0||(k1-k)==0)?0:*/(b-b1)/(k1-k);
		ll o=lower_bound(a1+1,a1+1+n,nx)-a1;
		if(o<1||o>n) continue;
		for(int j=max((ll)1,o-1);j<=max(n,o+1);++j){
     	//	e[++tot]=(ed){i+n,j,dis(x,y,a1[j],a1[j]*k1+b1)};//
     		e[++tot]=(ed){1,2,212};
		}	
		}
	for(int i=1;i<n;++i){
		e[++tot]=(ed){i,i+1,dis(a1[i],a1[i]*k1+b1,a1[i+1],a1[i+1]*k1+b1)};
	}
		for(int i=1;i<m;++i){
		e[++tot]=(ed){i+n,i+1+n,dis(a2[i],a2[i]*k1+b1,a2[i+1],a2[i+1]*k1+b1)};
	}
	//5m+n=6e5
	sort(e+1,e+1+tot,cmp);
	double sum=0;
	ll cnt=0;
       for(int i=1;i<=tot;++i){
		ll fu=find(e[i].u);
		ll fv=find(e[i].v);
		if(fu!=fv){
			f[fu]=fv;
			sum+=e[i].d;
			cnt++;
			if(cnt==n+m-1){
				break;
			}
		} 
	}
	printf("%.3lf\n",sum);
	return 0;
} 
2023/12/15 21:30
加载中...