社区讨论
求助代码厌氧(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 条回复,欢迎继续交流。
正在加载回复...