Pagini recente » Cod sursa (job #1941376) | Cod sursa (job #1163315) | Cod sursa (job #2159882) | Cod sursa (job #1042576) | Cod sursa (job #39386)
Cod sursa(job #39386)
# include <stdio.h>
# include <math.h>
# define _fin "regiuni.in"
# define _fout "regiuni.out"
# define maxn 3001
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];
char sgn[maxn][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);
}
for (i=1; i<=n; i++)
for (j=1; j<=m; j++)
sgn[i][j] = sign( a[j]*x[i]+b[j]*y[i]+c[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]) );
ok = ( sgn[i][k] == sgn[j][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;
}