【NOIP2016】愤怒的小鸟

题目链接

补档博客，无题解

Code:

#include<bits/stdc++.h>
#define rep(i,j,k) for(register int i=j;i<=k;i++)
#define double long double
using namespace std;
template<typename T> void chkmin(T &x,T y){x=x<y?x:y;}
template<typename T> void read(T &num){
    char c=getchar();num=0;T f=1;
    while(c<'0'||c>'9'){if(c=='-')f=-1;c=getchar();}
    while(c>='0'&&c<='9'){num=(num<<3)+(num<<1)+(c^48);c=getchar();}
    num*=f;
}
template<typename T> void qwq(T x){
    if(x>9)qwq(x/10);
    putchar(x%10+'0');
}
template<typename T> void write(T x){
    if(x<0){x=-x;putchar('-');}
    qwq(x);putchar('\n');
}
int n,m;
double co[20][2];int temp1[20];int temp2[20];

inline void work_out(double &a,double &b,double a1,double b1,double a2,double b2){\
    if(fabs(a1-a2)<=(1e-10)){
        a=0;b=0;return;
    }
    b=(a1*a1*b2-a2*a2*b1)/(a1*a1*a2-a2*a2*a1);a=(b1-a1*b)/(a1*a1);
    return;
}
inline int work(int a[]){
    double qa=0;double qb=0;double last1=co[a[1]][0];double last2=co[a[1]][1];
    int tmp=1;
    rep(i,2,n){
        if(!qa&&!qb){
            work_out(qa,qb,co[a[i]][0],co[a[i]][1],last1,last2);
            if(qa>0||(qa>-(1e-10)&&qa<(1e-10))){
                qa=0;qb=0;tmp++;	
            }
        }else{
            double nop=qa*(co[a[i]][0]*co[a[i]][0])+qb*co[a[i]][0];
            if(fabs(nop-co[a[i]][1])>=(1e-10)){
                tmp++;
                qa=0;qb=0;last1=co[a[i]][0];last2=co[a[i]][1];
            }
        }
    }
    return tmp;
}
inline bool Okay(double x,double y){
    if(x>=0)return true;
    return rand()<=exp((x)/y)*RAND_MAX;
}
inline int SA(){
    double temper=10000;
    random_shuffle(temp1+1,temp1+n+1);
    rep(i,1,n){temp2[i]=temp1[i];}
    int nop1=work(temp1);int nop2=nop1;int re_value=nop1;
    
    while(temper>0.01){
        int x=rand()%n+1;int y=rand()%n+1;
        if(x==y)continue;
        swap(temp2[x],temp2[y]);
        nop2=work(temp2);chkmin(re_value,nop2);
        if(Okay(nop1-nop2,temper)){
            swap(temp1[x],temp1[y]);nop1=nop2;
        }else{
            swap(temp2[x],temp2[y]);
        }
        temper*=0.99;
    }
    return re_value;
}

int main(){
    srand(time(NULL));
    int T;read(T);
    while(T--){
        read(n);read(m);
        rep(i,1,n){temp1[i]=i;}
        rep(i,1,n){cin>>co[i][0]>>co[i][1];}
        
        int ans=n;
        if(n<=4){
            do{
                int pos=work(temp1);
                chkmin(ans,pos);
            }while(next_permutation(temp1+1,temp1+n+1));
            write(ans);continue;
        }
        rep(i,1,80){
            chkmin(ans,SA());
        }
        write(ans);
    }
    return 0;
}