Pagini recente » Cod sursa (job #2830304) | Cod sursa (job #194148) | Cod sursa (job #2373248) | Cod sursa (job #66698) | Cod sursa (job #44834)
Cod sursa(job #44834)
#include <stdio.h>
#include <string.h>
#define FIN "regiuni.in"
#define FOUT "regiuni.out"
#define MAXN 1000
struct dr { int a, b, c; } D[MAXN];
struct punct { int x, y; } A[MAXN];
struct elem { int span; elem *r; } *start = new elem;
int n, m;
int Reg[MAXN], regs; // regiuni
int Reg2[MAXN];
// Regspan = cate elemente are acea regiune
// pe poz i in sirul de regiuni (Reg[]) se afla punctul Reg[i]
void rez()
{
int i, j, k, peste, st1;
elem *p;
for (i=0; i<m; ++i)
Reg[i] = i;
regs = 1;
start->r = new elem; start->r->span = m;
for (i=0; i<n; ++i) {
// luam fiecare regiune
for (p=start->r, j = 0, peste = 0; p; p = p->r, j += k) {
for (k=0; k < p->span; ++k)
peste += (D[i].a*A[Reg[j+k]].x + D[i].b*A[Reg[j+k]].y + D[i].c > 0);
if (peste == 0 || peste == p->span) continue;
// Grupul este divizat
++ regs;
elem *temp = new elem;
temp -> r = p->r;
p->r = temp;
memcpy(Reg2, &Reg[j], p->span * sizeof(int));
for (st1 = 0, k=0; k < p->span; ++k)
if (D[i].a*A[Reg[j+k]].x + D[i].b*A[Reg[j+k]].y + D[i].c > 0)
Reg[j+(st1++)] = Reg2[k];
else Reg[j+(peste++)] = Reg[k];
p->span = peste;
p = p->r;
p->span = k - peste;
}
}
printf("%d\n", regs);
}
void citire()
{
int i;
freopen(FIN, "r", stdin);
freopen(FOUT,"w",stdout);
scanf("%d %d\n", &n, &m);
for (i=0; i<n; ++i)
scanf("%d %d %d", &D[i].a, &D[i].b, &D[i].c);
for (i=0; i<m; ++i)
scanf("%d %d", &A[i].x, &A[i].y);
}
int main()
{
citire();
rez();
return 0;
}