Pagini recente » Cod sursa (job #12987) | Cod sursa (job #1025426) | Cod sursa (job #763398) | Cod sursa (job #3238804) | Cod sursa (job #41178)
Cod sursa(job #41178)
using namespace std;
#include<fstream>
#include<stdio.h>
#define nmax 1002
#define lmax 35
#define cst 30
int a[nmax],b[nmax],c[nmax];
struct nod{int x,y;nod* next;};
typedef nod* list;
list aa[1003],q;
struct sir{int x,y;};
sir g1[1003],g2[1003];
int ng1,ng2;
void bagagr1(int p)
{
int i;
for(i=1;i<=ng1;i++)
{
if(aa[p]==NULL)
{
aa[p]=new nod;
aa[p]->next=NULL;
}
else
{
q=new nod;
q->next=aa[p];
aa[p]=q;
}
aa[p]->x=g1[i].x;
aa[p]->y=g1[i].y;
}
}
void bagagr2(int p)
{
int i;
for(i=1;i<=ng2;i++)
{
if(aa[p]==NULL)
{
aa[p]=new nod;
aa[p]->next=NULL;
}
else
{
q=new nod;
q->next=aa[p];
aa[p]=q;
}
aa[p]->x=g2[i].x;
aa[p]->y=g2[i].y;
}
}
int main()
{
FILE *fin=fopen("regiuni.in","r"),
*fout=fopen("regiuni.out","w");
int m,n,i,j,k,ngr=1;
fscanf(fin,"%d%d",&n,&m);
for(i=1;i<=n;i++)
fscanf(fin,"%d%d%d",&a[i],&b[i],&c[i]);
for(i=1;i<=m;i++)
{
fscanf(fin,"%d%d",&j,&k);
if(aa[1]==NULL)
{
aa[1]=new nod;
aa[1]->next=NULL;
}
else
{
q=new nod;
q->next=aa[1];
aa[1]=q;
}
aa[1]->x=j;
aa[1]->y=k;
}
int noi;
for(i=1;i<=n;i++)
{
noi=0;
for(j=1;j<=ngr;j++)
{
ng1=ng2=0;
while(aa[j])
{
if(a[i]*aa[j]->x+b[i]*aa[j]->y+c[i]>0)
{
g1[++ng1].x=aa[j]->x;
g1[ng1].y=aa[j]->y;
}
else
{
g2[++ng2].x=aa[j]->x;
g2[ng2].y=aa[j]->y;
}
q=aa[j];
aa[j]=aa[j]->next;
delete q;
}
if(ng1>ng2)
{
bagagr1(j);
if(ng2)
{
noi++;
bagagr2(ngr+noi);
}
}
else
{
bagagr2(j);
if(ng1)
{
noi++;
bagagr1(ngr+noi);
}
}
}
ngr+=noi;
}
fprintf(fout,"%d\n",ngr);
fclose(fin);
fclose(fout);
return 0;
}