Pagini recente » Cod sursa (job #2944609) | Cod sursa (job #991582) | Cod sursa (job #3226400) | Cod sursa (job #2830810) | Cod sursa (job #37642)
Cod sursa(job #37642)
#include <stdio.h>
#include <stdlib.h>
#define nmax 1001
double A[nmax], B[nmax], C[nmax], X[nmax], Y[nmax];
int N, M, i, j, k, componente;
int V[nmax][nmax], suma[nmax], VIZ[nmax];
int *L[nmax];
void dfs(int x)
{
int i;
VIZ[x] = componente;
for (i = 1; i <= L[x][0]; ++i)
if (!VIZ[L[x][i]])
dfs(L[x][i]);
}
int main(void)
{
freopen("regiuni.in", "r", stdin);
freopen("regiuni.out", "w", stdout);
scanf("%d%d", &N, &M);
for (i = 1; i <= N; ++i)
scanf("%lf%lf%lf", &A[i], &B[i], &C[i]);
for (i = 1; i <= M; ++i)
scanf("%lf%lf", &X[i], &Y[i]);
for (i = 1; i <= M; ++i) // orice punct
for (j = 1; j <= N; ++j) // orice dreapta
{
V[i][j] = (A[j] * X[i] + B[j] * Y[i] + C[j]) > 0? 1: -1;
suma[i] = suma[i] + V[i][j];
}
for (i = 1; i <= M; ++i)
{
L[i] = (int *)realloc(L[i], sizeof(int));
L[i][0] = 0;
}
for (i = 1; i <= M; ++i)
for (j = i + 1; j <= M; ++j)
if (suma[i] == suma[j]) // este o probabilitate mare !
{
for (k = 1; k <= N && V[i][k] == V[j][k]; ++k);
if (k == N + 1)
{
L[i][0]++;
L[i] = (int *)realloc(L[i], (1 + L[i][0]) * sizeof(int));
L[i][L[i][0]] = j;
L[j][0]++;
L[j] = (int *)realloc(L[j], (1 + L[j][0]) * sizeof(int));
L[j][L[j][0]] = i;
}
}
for (i = 1; i <= M; ++i)
if (!VIZ[i])
{
componente++;
dfs(i);
}
printf("%d\n", componente);
return 0;
}