终于A掉了noip2016的Day2T3,至此,2015和2016的NOIP题都刷完了.

　　

　　写一下这道题卡常的过程吧.

　　真的只需要卡常啊.

　　

　　

　　m不用管了,反正奔着AC去的.

　　考虑怎么搜索?我们可以n^2的枚举所有的抛物线,再O(n)的枚举这条抛物线可以打掉哪些小猪.用一个二进制数存一下状态.

　　然后把所有的状态入队,答案设为1,然后开始bfs啦.

　　我们需要一些常数优化即可A掉本题.

struct node {    double x,y;}o[20];int tot,T,n,m,now,t;double a,b,eps=1e-10;double geta(node a,node b){    return (a.y*b.x/a.x-b.y)/(b.x*a.x-b.x*b.x);}double getb(double a,node b){    return b.y/b.x-a*b.x;}int can[1<<20],ans[1<<20];bool v[1<<20];queue
      
       q;inline void write(int x){    if(x==0){        putchar('0');                return;    }    if(x<0){        putchar('-');        x=-x;    }    int num=0;char ch[16];    while(x) ch[++num]=x%10+'0',x/=10;    while(num) putchar(ch[num--]);    }int main(){    for(scanf("%d",&T);T;--T)    {        scanf("%d%d",&n,&m);//久违的用scanf读入         for(register int i=1;i<=n;++i)//吹爆register!             scanf("%lf%lf",&o[i].x,&o[i].y);        tot=0;        for(register int i=1;i<=n;++i)        {            tot++;            can[tot]=1<
       
        =-eps)//如果a是负数就不要                     continue;                b=getb(a,o[i]);                tot++;can[tot]=0;                for(register int j=1;j<=n;j++)                    if(fabs(a*o[j].x*o[j].x+b*o[j].x-o[j].y)<=eps)                        can[tot]|=1<
        
         now&&ans[now]+1
        
       
      

　　吹爆register好吧,TLE秒变AC.(其实T掉的在本地跑也就是1.1s...)

>>>