社区讨论

求助代码厌氧(100->95)

P2831[NOIP 2016 提高组] 愤怒的小鸟参与者 3已保存回复 2

讨论操作

快速查看讨论及其快照的属性,并进行相关操作。

当前回复
2 条
当前快照
1 份
快照标识符
@m1spt0al
此快照首次捕获于
2024/10/03 11:06
去年
此快照最后确认于
2025/11/04 18:14
4 个月前
查看原帖
这份代码开O2会WA on #2
CPP
#include<bits/stdc++.h>
using namespace std;
int T,n,m,dx,NTT=114514,FFT,NOI,CCF,vis[25],l,r;
struct op{
	double x,y;
}d[25],xs;
op miHoYo(op ys,op xt){
	if(ys.x*ys.x*xt.x-xt.x*xt.x*ys.x==0||ys.y*xt.x-xt.y*ys.x==0){
		op CCF;CCF.x=CCF.y=0;
		return CCF;
	}
	op xs;
	xs.x=(ys.y*xt.x-xt.y*ys.x)/(ys.x*ys.x*xt.x-xt.x*xt.x*ys.x);
	xs.y=(ys.y-xs.x*ys.x*ys.x)/ys.x;
	if(xs.x>0)xs.x=xs.y=0;
	return xs;
}
int main(){
	cin>>T;NOI=500000/T;
	while(T--){
		cin>>n>>m;
		for(int i=1;i<=n;i++)scanf("%lf%lf",&d[i].x,&d[i].y);
		NTT=114514,CCF=NOI;
		while(CCF--){
			random_shuffle(d+1,d+n+1),FFT=0,dx=1;
			for(int i=0;i<25;i++)vis[i]=0;
			while(dx<=n){
				l=-1,r=-1;
				while(dx<=n&&r==-1){
					if(vis[dx]==0){
						vis[dx]=1;
						if(l==-1)l=dx;
						else r=dx;
					}
					dx++;
				}
				if(l==-1)break;
				if(r==-1)dx++,FFT++;
				else{
					xs=miHoYo(d[l],d[r]),dx=r,FFT++;
					if(xs.x==0){
						vis[r]=0,dx=l+1;
						continue;
					}
					for(int i=dx;i<=n;i++){
						if(abs(xs.x*d[i].x*d[i].x+xs.y*d[i].x-d[i].y)<1e-6){
							vis[i]=1;
						}
					}
				}
			}
			NTT=min(NTT,FFT);			
		}
		cout<<NTT<<endl;
	}
	return 0;
}
https://www.luogu.com.cn/record/179587220

回复

2 条回复,欢迎继续交流。

正在加载回复...