@[Erutsiom](/space/show?uid=64539) a<0 ~~不要出现反重力小鸟~~
by Hope2075 @ 2018-11-04 21:10:28
```
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
using namespace std;
#define ldb long double
const int MAXN=300005;
const int eps=1e-9;
const int inf=999999999;
int zt[MAXN],f[MAXN],t,n,m,cnt;
bool ok[MAXN];
ldb x[35],y[35];
ldb geta(ldb xa,ldb ya,ldb xb,ldb yb){
ldb ret=(xa*yb-xb*ya)/(xa*xb*(xb-xa));
return ret;
}
ldb getb(ldb xa,ldb ya,ldb xb,ldb yb){
ldb ret=(xb*xb*ya-xa*xa*yb)/(xa*xb*(xb-xa));
return ret;
}
bool judge(ldb xc,ldb yc,ldb aa,ldb bb){
if(fabs(yc-aa*xc*xc-bb*xc)<=eps)return 1;
return 0;
}
void init(){
memset(x,0,sizeof x);
memset(y,0,sizeof y);
memset(zt,0,sizeof zt);cnt=0;zt[0]=0;
memset(ok,0,sizeof ok);
memset(f,128/3,sizeof f);f[0]=0;
}
void getzt(){
for(int i=1;i<=n;i++){
cnt++;zt[cnt]=(1<<(i-1));
ok[(1<<(i-1))]=1;f[1<<(i-1)]=1;
}
for(int i=1;i<=n;i++)
for(int j=1;j<=n;j++){
if(i==j)continue;
if(x[i]==x[j])continue;
int tmp=(1<<(i-1))|(1<<(j-1));
if(ok[tmp])continue;
ldb nowa=geta(x[i],y[i],x[j],y[j]);
ldb nowb=getb(x[i],y[i],x[j],y[j]);
if(nowa>=-eps)continue;
cnt++;zt[cnt]=tmp;ok[tmp]=1;
f[tmp]=1;
for(int k=1;k<=n;k++){
if(k==i||k==j)continue;
if(abs(x[i]-x[k])<eps||abs(x[j]-x[k])<eps)continue;
if(judge(x[k],y[k],nowa,nowb)){
int tmmp=tmp|(1<<(k-1));
if(ok[tmmp])continue;
tmp=tmmp;
cnt++;zt[cnt]=tmp;ok[tmp]=1;f[tmp]=1;
}
}
}
}
int dfs(int noww){
if(f[noww]<23333)return f[noww];
for(int i=1;i<=cnt;i++){
if((noww|zt[i])==noww){
int tmpp=noww^zt[i];
dfs(tmpp);
f[noww]=min(f[noww],f[tmpp]+1);
}
}return f[noww];
}
void work1(){
int ans=n;
if(m==1){
if(n%3==0)ans=n/3+1;
else ans=n/3+2;
}
printf("%d\n",min(ans,dfs((1<<n)-1)));
}
int main(){
scanf("%d",&t);
while(t--){
scanf("%d%d",&n,&m);
init();
if(n<=2){
for(int i=1;i<=n;i++){
cin>>x[i]>>y[i];
}
if(n==0){
printf("0\n");continue;}
ldb qa=geta(x[1],y[1],x[2],y[2]);
if(qa>=-eps)printf("2\n");
else printf("1\n");
continue;
}
for(int i=1;i<=n;i++){
cin>>x[i]>>y[i];
}
if(n==3){
ldb qa=geta(x[1],y[1],x[2],y[2]);
ldb qb=getb(x[1],y[1],x[2],y[2]);
if(judge(x[3],y[3],qa,qb)){
if(qa>=0)printf("3\n");
else printf("1\n");
}
else if(qa<0)printf("2\n");
else{
if(geta(x[1],y[1],x[3],y[3])<0||geta(x[3],y[3],x[2],y[2])<0)
printf("2\n");
else printf("3\n");
}
continue;
}
getzt();
work1();
}return 0;
}
```
by Erutsiom @ 2018-11-04 21:13:51
@[i_m_a_](/space/show?uid=86649) 嗯嗯判了qwq不判似乎更低
by Erutsiom @ 2018-11-04 21:14:38
第五组数据第六个讯问
我的程序跑出3
答案2
~~几何画板目测1~~
by Erutsiom @ 2018-11-04 21:16:37
@[Erutsiom](/space/show?uid=64539) 过了没，同卡#5、#8...
by diker @ 2018-12-03 21:08:09
@[Erutsiom](/space/show?uid=64539) 精度，double再乘一个100扩大可以过。。。
by diker @ 2018-12-03 23:06:30