Pagini recente » Cod sursa (job #517872) | Cod sursa (job #2618868) | Cod sursa (job #1854753) | Cod sursa (job #568098) | Cod sursa (job #50002)
Cod sursa(job #50002)
#include <cstdio>
#include <vector>
#include <list>
#include <string>
#include <iterator>
#define INF "regiuni.in"
#define OUF "regiuni.out"
#define NMAX 1024
#define LMAX 1024
#define pb push_back
using namespace std;
/*struct muchie
{
int a,b,c;
};
struct point
{
int x,y;
};*/
int main()
{
FILE *in,*out;
in=fopen(INF,"r");
out=fopen(OUF,"w");
int i,j,k,x,y,n,m;
int nr,dim,sel;
int use[LMAX]={0};
int a[NMAX],b[NMAX],c[NMAX],xx[NMAX],yy[NMAX];
vector<int> gr[LMAX],st,dr;
vector<int>::iterator ti;
list<int> next;
list<int>::iterator it;
// muchie ed[NMAX];
// point pt[NMAX];
fscanf(in,"%d %d",&n,&m);
sel=1;
for(i=1;i<=n;i++) fscanf(in,"%d %d %d",a+i,b+i,c+i);
for(i=1;i<=m;i++)
{
fscanf(in,"%d %d",xx+i,yy+i);
gr[1].pb(i);use[i]=0;next.pb(i);
}
use[1]=1;next.pop_front();it=next.begin();
for(i=1;i<=n;i++)
{
for(j=1;j<=m;j++)
{
if(use[j]==i)
{
// nr=0;ko=0;
dim=gr[j].size();
for(k=0;k<dim;k++)
{
x=xx[gr[j][k]];y=yy[gr[j][k]];
if(a[i]*x+b[i]*y+c[i]>0) dr.pb(gr[j][k]);
else st.pb(gr[j][k]);
}
use[j]=0;gr[j].clear();
next.pb(j);
if(!st.empty())
{
sel=(*it);it++;
next.pop_front();
gr[sel]=st;use[sel]=i+1;
st.clear();
}
if(!dr.empty())
{
sel=(*it);it++;
next.pop_front();
gr[sel]=dr;use[sel]=i+1;
dr.clear();
}
}
}
}
nr=0;
// printf("%d",gr[4].size());
for(i=1;i<=m;i++)
{
if(!gr[i].empty())
{
nr++;
// dim=gr[i].size();
// for(j=0;j<dim;j++) printf("%d ",gr[i][j]);
// printf("\n");
}
}
fprintf(out,"%d",nr);
fclose(in);fclose(out);
return 0;
}