Cod sursa(job #40468)
Utilizator | Data | 27 martie 2007 14:10:18 | |
---|---|---|---|
Problema | Regiuni | Scor | 0 |
Compilator | cpp | Status | done |
Runda | Arhiva de probleme | Marime | 4.14 kb |
#include <stdio.h>
#define dim 1001
int Nd, Np, Sol;
int A[dim], B[dim], C[dim], X[dim], Y[dim];
struct grup
{ int nd; grup *next; } *G[dim];
void Read();
void Solve();
void Write();
void Add(grup *&, int);
int main()
{
Read();
Solve();
Write();
return 0;
}
void Read()
{
freopen("regiuni.in", "r", stdin);
scanf("%d %d", &Nd, &Np);
int i;
for(i=1; i<=Nd; ++i)
scanf("%d %d %d", A+i, B+i, C+i);
for(i=1; i<=Np; ++i)
scanf("%d %d", X+i, Y+i);
fclose(stdin);
}
void Add(grup *&G, int nd)
{
grup *x = new grup;
x->nd = nd;
x->next = G;
G = x;
}
void Solve()
{
int i, j, c1, c2, limit, up; long conf;
grup *prec;
for(i=1; i<=Np; ++i)
Add(G[1], i);
Sol = 1;
for(i=1; i<=Nd; ++i)
{
limit = Sol;
for(j=1; j<=limit; ++j)
{
grup *x;
c1 = c2 = 0;
up = 0;
x = G[j];
while(x)
{
conf = A[i]*X[x->nd] + B[i]*Y[x->nd] + C[i];
if(conf > 0) c1 = 1;
if(conf < 0) c2 = 1;
if(c1+c2 == 2) break;
x = x->next;
}
if(c1+c2 == 2)
{
x = G[j];
prec = NULL;
while(x)
{
conf = A[i]*X[x->nd] + B[i]*Y[x->nd] + C[i];
if(conf < 0)
{
up = 1;
Add(G[Sol+1], x->nd);
if(x == G[j])
{
grup *p = x;
x = x->next;
delete p;
}
else
{
if(x->next == NULL)
{
if(prec != NULL)
prec->next = NULL;
delete x;
x = NULL;
}
else
{
prec->next = x->next;
grup *p = x;
x = x->next;
delete p;
}
}
}
else
{
prec= x;
x = x->next;
}
}
}
Sol += up;
}
}
}
void Write()
{
freopen("regiuni.out", "w", stdout);
printf("%d", Sol);
fclose(stdout);
}