春季赛T3暴力+clock能骗90pts???
  • 板块学术版
  • 楼主Tjqq
  • 当前回复4
  • 已保存回复4
  • 发布时间2023/3/5 20:57
  • 上次更新2023/10/23 22:54:57
查看原帖
春季赛T3暴力+clock能骗90pts???
540665
Tjqq楼主2023/3/5 20:57

有人能帮我再卡一卡吗

#include<cstdio>
#include<iostream>
#include<vector>
#include<cstring>
#include<cmath>
#include<algorithm>
#define db double
#define IOS ios::sync_with_stdio(false);cin.tie(0); 
#include<ctime>
//#include<cstdlib>
#define ll long long
#define INF_INT 0x3f3f3f3f
char Ch;
int ff;
inline void rd(int &x){
	x=0,ff=1,Ch=getchar();
	while((Ch<'0'||Ch>'9')&&Ch!='-')Ch=getchar();
	if(Ch=='-')Ch=getchar(),ff=-1;
	while(Ch>='0'&&Ch<='9'){
		x=(x<<1)+(x<<3)+Ch-'0';
		Ch=getchar();
	}
	x*=ff;
}
inline int random(int x){
	return (long long)rand()*rand()%x;
}
using namespace std;
const int N=1e3+5;
int n,k,tp;
double mx=-2e7; 
db x[N],y[N],Ans=1e20;
int a[N],ans[N],flag;
bool vis[N];
vector<pair<double,int> >v[N];
inline db work(db ax,db ay,db bx,db by){
	return sqrt((ax-bx)*(ax-bx)+(ay-by)*(ay-by));
}
void dfs(int dep,db s){
	if(flag)return ;
	if(s>Ans)return ;
	if(n>=18&&clock()>500000)return flag=1,void();
	if(dep==n+1){
		Ans=s;
		memcpy(ans,a,sizeof(a));
		return ;
	}
	for(auto j:v[a[dep-1]]){ 
		int i=j.second,w=j.first;
		if(!vis[i]){
			vis[i]=1;
			a[dep]=i;
			dfs(dep+1,s+w);
			vis[i]=0;
		}
	}
}
signed main(){
//	srand(time(0));
//	freopen(".in","r",stdin);
//	freopen(".out","w",stdout);
	IOS
	cin>>n;
	tp=clock();
	for(int i=1;i<=n;i++){
		cin>>x[i]>>y[i];
		if(y[i]>=mx)mx=y[i],k=i;
	}
	for(int i=1;i<=n;i++)
		for(int j=i+1;j<=n;j++){
			v[i].emplace_back(make_pair(work(x[i],y[i],x[j],y[j]),j));
			v[j].emplace_back(make_pair(work(x[i],y[i],x[j],y[j]),i));
		}
	if(n>4)
		for(int i=1;i<=n;i++)
			sort(v[i].begin(),v[i].end());
	a[1]=k;
	vis[k]=1;
	dfs(2,0);
	for(int i=1;i<=n;i++)
		printf("%d ",ans[i]);
	return 0;
}
2023/3/5 20:57
加载中...