Cod sursa(job #37572)

Utilizator m_dersidanDersidan Mihai m_dersidan Data 25 martie 2007 11:05:31
Problema Regiuni Scor 70
Compilator cpp Status done
Runda preONI 2007, Runda 4, Clasele 11-12 Marime 1.86 kb
# include <stdio.h>
# include <math.h>

# define  _fin	"regiuni.in"
# define  _fout "regiuni.out"

# define  maxn	1001


double dp[maxn][maxn], dl[maxn], aux;
int x[maxn], y[maxn], 					// puncte
	a[maxn], b[maxn], c[maxn],			// linii
	m, n, i, j, k, ok, sol,
	p[maxn], rang[maxn], mult[maxn];	// multimile


void uneste(int x, int y)
{
	if ( rang[x]<rang[y] ) p[x]=y;
	else p[y]=x, rang[x]+=(rang[x]==rang[y]);
}
int par(int x)
{
	if ( p[x]!=x ) p[x]=par(p[x]);
	return p[x];
}
void reuneste(int x, int y)
{
	uneste(par(x), par(y));
}

inline double dpp(int i, int j) { return sqrt( (x[i]-x[j])*(x[i]-x[j]) + (y[i]-y[j])*(y[i]-y[j]) ); }
inline double abs(double x) { return x>0?x:-x; }
inline double dpl(int i, int j) { return abs(a[j]*x[i]+b[j]*y[i]+c[j]) / sqrt(a[j]*a[j]+b[j]*b[j]); }
inline int sign(int x) { return x>0?1:-1; }

void readf()
{
	freopen(_fin, "r", stdin);
	for (scanf("%d%d", &m, &n), i=1; i<=m; i++) scanf("%d%d%d", a+i, b+i, c+i);
	for (i=1; i<=n; i++) scanf("%d%d", x+i, y+i);
}

void presolve()
{
	for (i=1; i<=n; i++) {
		p[i]=i;
		dl[i] = dpl(i, 1);
		for (j=2; j<=m; j++) {
			aux=dpl(i, j);
			if ( aux<dl[i] ) dl[i]=aux;
		}
	}
	
	for (i=1; i<=n; i++)
		for (j=i+1; j<=n; j++) {
			if ( par(i)==par(j) ) continue;
			aux=dpp(i, j);
			if ( aux<=dl[i] || aux<=dl[j] ) reuneste(i, j);
		}
}

void solve()
{
	for (i=1; i<=n; i++)
		for (j=i+1; j<=n; j++) {
			if ( par(i)==par(j) ) continue;
			for (ok=k=1; k<=m && ok; k++)
				ok = ( sign(a[k]*x[i]+b[k]*y[i]+c[k]) == sign(a[k]*x[j]+b[k]*y[j]+c[k]) );
			if ( ok ) reuneste(i, j);
		}
	
	for (i=1; i<=n; i++)
		++mult[ par(i) ];
	for (i=1; i<=n; i++)
		sol += (!!mult[i]);
}

int main()
{
	readf();
	freopen(_fout,"w", stdout);
	if ( m ) {
		presolve();
		solve();
		printf("%d\n", sol);
	}
	else
		printf("%d\n", 1);
	
	return 0;
}