Cod sursa(job #40803)
Utilizator | Data | 27 martie 2007 19:10:51 | |
---|---|---|---|
Problema | Regiuni | Scor | 100 |
Compilator | cpp | Status | done |
Runda | Arhiva de probleme | Marime | 2.04 kb |
#include <stdio.h>
#define dim 1001
int Nd, Np, Sol;
int A[dim], B[dim], C[dim], X[dim], Y[dim], G[dim], P[dim], N[dim], Ng[dim];
void Read();
void Solve();
void Write();
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 Solve()
{
int i, j, config;
for(i=1; i<=Np; ++i)
G[i] = 1;
Sol = 1;
for(i=1; i<=Nd; ++i)
{
for(j=1; j<=Sol; ++j)
P[j] = N[j] = Ng[j] = 0;
for(j=1; j<=Np; ++j)
{
config = A[i]*X[j] + B[i]*Y[j] + C[i];
if(config > 0)
P[G[j]] = 1;
if(config < 0)
N[G[j]] = 1;
}
for(j=1; j<=Np; ++j)
if(P[G[j]] && N[G[j]])
{
config = A[i]*X[j] + B[i]*Y[j] + C[i];
if(config < 0)
{
if(!Ng[G[j]])
{
Ng[G[j]] = ++ Sol;
G[j] = Ng[G[j]];
}
else
G[j] = Ng[G[j]];
}
}
}
}
void Write()
{
freopen("regiuni.out", "w", stdout);
printf("%d", Sol);
fclose(stdout);
}