Pagini recente » Cod sursa (job #1693971) | Cod sursa (job #1599398) | Cod sursa (job #3280160) | Monitorul de evaluare | Cod sursa (job #47487)
Cod sursa(job #47487)
#include <cstdio>
#include <vector>
#include <list>
#include <string>
#define INF "regiuni.in"
#define OUF "regiuni.out"
#define NMAX 1024
#define LMAX 2048
#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,oldim,dim,nr,ko;
char gone[LMAX]={0};
list<int> gr[LMAX];
list<int>::iterator it,del;
muchie ed[NMAX];
point pt[NMAX];
fscanf(in,"%d %d",&n,&m);
dim=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[dim].pb(i); }
for(i=1;i<=n;i++)
{
oldim=dim;
for(op=1;op<=oldim;op++)
{
if(!gone[op])
{
nr=0;ko=0;
for(it=gr[op].begin();it!=gr[op].end();it++)
{
if(ko)
{
gr[op].erase(del);
ko=0;
}
x=pt[(*it)].x;y=pt[(*it)].y;
if(ed[i].a*x+ed[i].b*y+ed[i].c>0)
{
if(!nr)//grup nou
{
nr++;
dim++;
}
gr[dim].pb(*it);
ko=1;del=it;
}
}
if(ko)
{
gr[op].erase(del);
ko=0;
}
if(gr[op].empty()) gone[op]=1;
}
}
}
nr=0;
//printf("%d",dim);
for(i=1;i<=dim;i++) if(!gone[i]) nr++;
fprintf(out,"%d",nr);
fclose(in);fclose(out);
return 0;
}