Cod sursa(job #37641)

Utilizator vmaneavmanea vmanea Data 25 martie 2007 11:35:39
Problema Regiuni Scor 100
Compilator c Status done
Runda preONI 2007, Runda 4, Clasa a 10-a Marime 1.43 kb
#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;
}