此题为什么不能贪心
统计出任意两个点上抛物线经过的点的个数,每次取最大的,然后把其他线上已被经过的点删掉,重复直到所有点都被经过
30分代码
#include<bits/stdc++.h>
using namespace std;
struct lines
{
int num;
bool sf[19];
};
lines li[1001];
double ah[20][2];
bool cmp(lines a,lines b)
{
return a.num>b.num;
}
int main()
{
//freopen("angrybirds.in","r",stdin);
//freopen("angrybirds.out","w",stdout);
int t;
cin>>t;
while(t--)
{
int n,m;
cin>>n>>m;
for(int i=1;i<=n;i++) cin>>ah[i][0]>>ah[i][1];
for(int i=1;i<=n;i++)
{
for(int j=1;j<=n;j++)
{
if(i>=j)
{
li[(i-1)*n+j].num=-999;
continue;
}
double a,b;
double x1=ah[i][0],y1=ah[i][1],x2=ah[j][0],y2=ah[j][1];
a=(y1-y2*x1/x2)/(x1*(x1-x2));
b=(y1-a*x1*x1)/x1;
if(a>=0)
{
li[(i-1)*n+j].num=-999;
continue;
}
bool flag=0;
for(int k=1;k<j;k++)
{
if(k==i) continue;
if(a*ah[k][0]*ah[k][0]+b*ah[k][0]==ah[k][1])
{
flag=1;
break;
}
}
if(flag)
{
li[(i-1)*n+j].num=-999;
continue;
}
li[(i-1)*n+j].sf[i]=1;
li[(i-1)*n+j].sf[j]=1;
li[(i-1)*n+j].num=2;
for(int k=j+1;k<=n;k++)
{
if(ah[k][0]*ah[k][0]*a+b*ah[k][0]==ah[k][1])
{
li[(i-1)*n+j].num++;
li[(i-1)*n+j].sf[k]=1;
}
}
}
}
int ahh=n;
int cnt=0;
while(ahh>0)
{
sort(li+1,li+n*n+1,cmp);
if(li[1].num<=0)
{
cnt+=ahh;
break;
}
ahh-=li[1].num;
li[1].num=-999;
for(int i=1;i<=n;i++)
{
if(li[1].sf[i])
{
for(int j=2;j<=n*n;j++)
{
if(li[j].sf[i])
{
li[j].num--;
li[j].sf[i]=0;
}
}
li[1].sf[i]=0;
}
}
cnt++;
}
cout<<cnt<<endl;
}
return 0;
}