PIZZALOC - Pizza Location
Tác giả: hieult
Ngôn ngữ: C++
#include <stdio.h>
//#include <conio.h>
struct toado
{
int x,y;
};
struct cuahang
{
public:
int sch,a[101];
};
int main()
{
//freopen("PIZZALOC.in","r",stdin);
int k,r,m,n,nguoi[101];
toado A[21],B[101];
cuahang ch[21];
scanf("%d %d",&k,&r);
scanf("%d",&m);
for(int i = 1;i<=m;i++)
{
//printf("1\n");
//ch[i].sch = 0;
scanf("%d %d",&A[i].x,&A[i].y);
}
// printf("2\n");
scanf("%d",&n);
for(int i = 1;i<=n ; i++)
scanf("%d %d %d",&B[i].x,&B[i].y,&nguoi[i]);
for(int i = 1;i<=m;i++)
{
// printf("3\n");
ch[i].sch = 0;
// printf("4\n");
for(int j = 1;j<=n;j++)
if((A[i].x-B[j].x)*(A[i].x-B[j].x)+(A[i].y-B[j].y)*(A[i].y-B[j].y)<= r*r)
{
ch[i].sch++;
ch[i].a[ch[i].sch] = j;
}
}
int u[k+1],flag[101],KQ = 0;
for(int i = 1;i<=k;i++)
u[i] = i;
while(true)
{
//for(int i = 1;i<=k;i++) printf("%d ",u[i]);
//printf("\n");
int max = 0;
for(int i = 1 ;i<=n;i++)
flag[i] = 0;
for(int i = 1;i<=k;i++)
for(int j = 1;j<=ch[u[i]].sch;j++)
if(flag[ch[u[i]].a[j]]==0)
{
flag[ch[u[i]].a[j]]=1;
max = max + nguoi[ch[u[i]].a[j]];
}
// printf("_____%d____\n",max);
if(max>KQ)
KQ = max;
if(u[k]<m)
u[k]++;
else
{
int fl = k-1;
while(fl>0)
{
if(u[fl]+1!=u[fl+1])
break;
fl--;
}
if(fl==0)
break;
else
{
u[fl]++;
for(int i = fl+1;i<=k;i++)
u[i] = u[i-1]+1;
}
}
}
printf("%d",KQ);
//getch();
}