请问这是哪道题
by wxy_god @ 2018-07-18 21:06:09
哎，夏令营将过这题，没听懂。。。
~~小数，精度什么的最讨厌了~~
by xiangling @ 2018-07-18 21:15:35
对就是~~不存在~~的精度问题，我这道题eps=1e-7就会wa成70,1e-5就会AC，自己意会
by AcerMo @ 2018-07-18 21:20:46
~~这题不是状态压缩吗。。精度问题不大吧~~
by moye到碗里来 @ 2018-07-18 21:21:10
~~看错题了当我没说~~
by AcerMo @ 2018-07-18 21:22:55
~~开double试一下~~
by AcerMo @ 2018-07-18 21:23:18
您怕不是在fAKe
by AcerMo @ 2018-07-18 21:28:18
@[_Acer_](/space/show?uid=71558) 请问您的浏览器背景怎么弄的
by 氷スイカ233 @ 2018-07-18 21:47:03
@[_Acer_](/space/show?uid=71558) emmmm好像是注释的时候出了点错误
```cpp
#include<cstdio>
#include<algorithm>
#include<cstring>
#define LL long long
using namespace std;
int t,n,f[1<<18],curve[20][20];
LL x[20],y[20];
void calc(int i,int j)
{
LL a1=x[i]*y[j]-x[j]*y[i];
LL a2=x[i]*x[j]*x[j]-x[i]*x[i]*x[j];
LL b1=x[j]*x[j]*y[i]-x[i]*x[i]*y[j];
LL b2=x[i]*x[j]*x[j]-x[i]*x[i]*x[j];
if(a1==0||a2==0||b2==0)return;
if(a1<0&&a2<0||a1>0&&a2>0)return;
for(int k=1;k<=n;k++)
{
if(a1*b2*x[k]*x[k]+a2*b1*x[k]==a2*b2*y[k])
curve[i][j]|=(1<<k-1);
}
}
void pre()
{
memset(curve,0,sizeof(curve));
for(int i=1;i<=n;i++)
for(int j=1;j<=n;j++)
calc(i,j);
}
int main()
{
scanf("%d",&t);
while(t--)
{
scanf("%d%*d",&n);
for(int i=1;i<=n;i++)
{
double xx,yy;
scanf("%lf%lf",&xx,&yy);
x[i]=xx*100;
y[i]=yy*100;
}
pre();
memset(f,0x7f,sizeof(f));
f[(1<<n)-1]=0;
for(int i=(1<<n)-1;i>0;i--)
{
if(f[i]>n)continue;
int first=0;
while(((1<<first)&i)==0)first++;
first++;
for(int j=first+1;j<=n;j++)
{
if(((1<<j-1)&i)==0)continue;
int next=(i^(curve[first][j]&i));
f[next]=min(f[next],f[i]+1);
}
int next=i^(1<<first-1);
f[next]=min(f[next],f[i]+1);
}
printf("%d\n",f[0]);
}
return 0;
}
```
by wucstdio @ 2018-10-10 14:41:42