[LOJ] #2363「NOIP2016」愤怒的小鸟

提示：扫一扫查出行
【扫一扫了解最新限行尾号】
复制提示

精度卡了一个点，别人自带大常数，我自带大浮点误差qwq.

听了好几遍，一直没动手写一写。

f[S]表示S集合中的猪被打死的最少抛物线数，转移时考虑枚举两个点，最低位的0为第一个点，枚举第二个点，构造一条抛物线。

检查这条抛物线能否“顺便”打死更多的猪，然后转移即可。

注意存在一种情况，只剩下一个点，这时候要给最低位0单独开一条抛物线（体现在代码里就是f[i|(1<<(st-1))]单独转移一次）

//失误 这是一个

#include<iostream>

#include<cstring>

#include<cstdio>

#include<cmath>

using namespace std;

typedef long double db;

const int MAXN=;

const db eps=1e-;

inline void calc(db x1,db y1,db x2,db y2,db &a,db &b){

  a=(db)1.0*(x1*y2-x2*y1)/(x1*x2*(x2-x1));

  b=(db)1.0*(x1*x1*y2-x2*x2*y1)/(x1*x2*(x1-x2));

}

inline db F(db a,db b,db x){return (db)1.0*a*x*x+1.0*b*x;}

inline bool equal(db x,db y){return fabs(x-y)<=eps;}

int n,useless;

db px[MAXN],py[MAXN];

int f[<<MAXN];

void solve(){

  scanf("%d%d",&n,&useless);

  memset(f,0x7f,sizeof(f));

  f[]=;

  for(int i=;i<=n;i++) scanf("%Lf%Lf",&px[i],&py[i]);

  int st=;db u,v;

  for(int i=;i<(<<n);i++){

    for(st=;st<=n;st++)if(!((<<(st-))&i))break;

    f[i|(<<(st-))]=min(f[i|(<<(st-))],f[i]+);

    for(int j=st+;j<=n;j++){

      if((<<(j-))&i) continue;

      int tmp=i|(<<(st-));

      calc(px[st],py[st],px[j],py[j],u,v);

      if(u>=) continue;

      tmp|=(<<(j-));

      for(int k=;k<=n;k++){

        if(k==j||k==st) continue;

        if(i&(<<(k-))) continue;

        if(equal(F(u,v,px[k]),py[k])) tmp|=(<<(k-));

      }

      f[tmp]=min(f[tmp],f[i]+);

    }

  }

  cout<<f[(<<n)-]<<endl;

}

int main(){

  int T;

  scanf("%d",&T);

  while(T--) solve();

  return ;

}