# 斯德哥尔摩 的博客

### P2831 愤怒的小鸟

posted on 2018-10-29 23:31:59 | under 刷题 |

P2831 愤怒的小鸟

$No.1$：

$No.2$：

$$b=\frac{y_1}{x_1}-\frac{x_2y_1-x_1y_2}{x_2(x_1-x_2)}=\frac{y_1}{x_1}-ax_1$$

#include<iostream>
#include<algorithm>
#include<cstdio>
#include<cmath>
#include<cstring>
#define MAXN 20
#define eps (1e-8)
using namespace std;
int n,S,special;
int line[MAXN][MAXN],lowestbit[1<<MAXN],dp[1<<MAXN];
struct Pig{
double x,y;
friend bool operator <(const Pig &p,const Pig &q){
if(p.x==q.x)return p.y<q.y;
return p.x<q.x;
}
}a[MAXN];
int date=0,w=1;char c=0;
while(c<'0'||c>'9'){if(c=='-')w=-1;c=getchar();}
while(c>='0'&&c<='9'){date=date*10+c-'0';c=getchar();}
return date*w;
}
void make(){//预处理
for(int i=0;i<(1<<18);i++){
int j;
for(j=1;j<=18&&(i&(1<<(j-1)));j++);
lowestbit[i]=j;
}
}
void init(){
S=(1<<n);
for(int i=1;i<=n;i++)scanf("%lf%lf",&a[i].x,&a[i].y);
sort(a+1,a+n+1);
memset(dp,127,sizeof(dp));
memset(line,0,sizeof(line));
for(int i=1;i<=n;i++)
for(int j=1;j<=n;j++){//暴力判二次函数
if(a[i].x==a[j].x)continue;
double A=(a[i].y*a[j].x-a[i].x*a[j].y)/(a[i].x*a[j].x*(a[i].x-a[j].x));
double B=a[i].y/a[i].x-a[i].x*A;
if(A>-eps)continue;
line[i][j]=(1<<(i-1))|(1<<(j-1));
for(int k=1;k<=n;k++){
if(i==k||j==k)continue;
double y=a[k].x*a[k].x*A+a[k].x*B;
if(fabs(y-a[k].y)<eps)line[i][j]|=(1<<(k-1));
}
}
}
void work(){
dp[0]=0;
for(int s=0;s<S;s++){
int i=lowestbit[s];
dp[s|(1<<(i-1))]=min(dp[s|(1<<(i-1))],dp[s]+1);
for(int j=1;j<=n;j++)dp[s|line[i][j]]=min(dp[s|line[i][j]],dp[s]+1);
}
printf("%d\n",dp[S-1]);
}
int main(){
make();
while(t--){
init();
work();
}
return 0;
}