Pagini recente » Cod sursa (job #2269736) | Cod sursa (job #30540) | Cod sursa (job #1245646) | Cod sursa (job #3197328) | Cod sursa (job #49976)
Cod sursa(job #49976)
#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 op,nr,ko,dim,sel;
int use[LMAX]={0};
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",&ed[i].a,&ed[i].b,&ed[i].c);
for(i=1;i<=m;i++)
{
fscanf(in,"%d %d",&pt[i].x,&pt[i].y);
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;
for(k=0;k<gr[j].size();k++)
{
x=pt[gr[j][k]].x;y=pt[gr[j][k]].y;
if(ed[i].a*x+ed[i].b*y+ed[i].c>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;
}