# 【noip2016】愤怒的小鸟

Kiana最近沉迷于一款神奇的游戏无法自拔。

2
2 0
1.00 3.00
3.00 3.00
5 2
1.00 5.00
2.00 8.00
3.00 9.00
4.00 8.00
5.00 5.00

1
1

#include<cmath>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
#define ll long long

const int maxn=(1<<19);
const double eps=1e-8;

int n,m,T,state[20][20],judge[20],dp[maxn];

struct Pig{double x,y;}a[20];

int calc(int d1,int d2){
double x1=a[d1].x,y1=a[d1].y;
double x2=a[d2].x,y2=a[d2].y;
if(fabs(x1-x2)<=eps) return 0;
double tx=x1*x1*x2-x2*x2*x1,ty=y1*x2-y2*x1;
double aa=ty/tx,b=(y1-aa*x1*x1)/x1;
if(aa>=0) return 0;
int res=0;
judge[d1]=judge[d2]=1;
for(int i=1;i<=n;i++){
double x=a[i].x,y=a[i].y;
if(fabs(aa*x*x+b*x-y)<eps)
res|=1<<(i-1),dp[1<<(i-1)]=dp[res]=1;
}
return res;
}

char cc; ll ff;aa=0;cc=getchar();ff=1;
while((cc<‘0‘||cc>‘9‘)&&cc!=‘-‘) cc=getchar();
if(cc==‘-‘) ff=-1,cc=getchar();
while(cc>=‘0‘&&cc<=‘9‘) aa=aa*10+cc-‘0‘,cc=getchar();
aa*=ff;
}

int main(){
while(T--){
memset(dp,127,sizeof(dp));
memset(judge,0,sizeof(judge));
for(int i=1;i<=n;i++){
scanf("%lf%lf",&a[i].x,&a[i].y);
dp[1<<(i-1)]=1;
}
for(int i=1;i<=n;i++)
for(int j=i+1;j<=n;j++)
state[i][j]=calc(i,j);
for(int i=1;i<(1<<n);i++)
for(int j=1;j<=n;j++){
if(((i>>(j-1))&1)) continue;
if(!judge[j]){
dp[i|(1<<(j-1))]=min(dp[i|1<<(j-1)],dp[i]+1);
continue;
}
for(int k=j+1;k<=n;k++){
if(((i>>(k-1))&1)) continue;
dp[i|state[j][k]]=min(dp[i|state[j][k]],dp[i]+1);
}
dp[i|(1<<(j-1))]=min(dp[i|1<<(j-1)],dp[i]+1);
}
printf("%d\n",dp[(1<<n)-1]);
}
return 0;
}

【noip2016】愤怒的小鸟

(0)
(0)