Cod sursa(job #286348)

Utilizator rupraRupra C rupra Data 23 martie 2009 18:25:53
Problema Regiuni Scor 100
Compilator cpp Status done
Runda aa Marime 1.44 kb
#include <algorithm>
#include <stdio.h>

#define pb push_back
#define mp make_pair
#define MAX 1024
#define f first
#define s second

using namespace std;

int n, m;
int coefA[MAX], coefB[MAX], coefC[MAX];
int cX[MAX], cY[MAX];
int grupaS[MAX], sch[MAX];
pair <int, int> elemGr[MAX];

inline int sgn(long double x)
{
	if (x < 0)
		return -1;
	if (x > 0)
		return 1;
	return 0;
}

int main()
{
	freopen("regiuni.in", "r", stdin);
	freopen("regiuni.out", "w", stdout);

	scanf("%d %d", &n, &m);

	for (int i = 1; i <= n; i++)
		scanf("%d %d %d", &coefA[i], &coefB[i], &coefC[i]);

	for (int i = 1; i <= m; elemGr[i] = mp(1, i), i++)
		scanf("%d %d", &cX[i], &cY[i]);

	int nrGrupe = 1;
	for (int dr = 1; dr <= n; dr++)
	{
		for (int i = 1; i <= m; i++)
		{
			double s1 = (cX[i] * coefA[dr]) + (cY[i] * coefB[dr]) + coefC[dr];

			if (sgn(s1) == 1)
				grupaS[i] = 1;
			else grupaS[i] = 2;
		}

		for (int i = 1, gn, s1; i <= m; i++)
		{
			if (elemGr[i].f != elemGr[i - 1].f)
				s1 = grupaS[elemGr[i].s], gn = 0, sch[i] = elemGr[i].f;
			else
			{
				if (grupaS[elemGr[i].s] != s1)
				{
					if (gn)
						sch[i] = nrGrupe;
					else sch[i] = (++nrGrupe);

					gn = 1;
				}

				else sch[i] = elemGr[i].f;
			}
		}

		for (int i = 1; i <= m; i++)
			elemGr[i].f = sch[i];

		sort(elemGr + 1, elemGr + 1 + m);
	}

	printf("%d\n", nrGrupe);

	fclose(stdin);
	fclose(stdout);
	return 0;
}