Pagini recente » Cod sursa (job #1334554) | Cod sursa (job #1307670) | Cod sursa (job #518836) | Cod sursa (job #1556097) | Cod sursa (job #37518)
Cod sursa(job #37518)
#include<stdio.h>
int n, m, reg[1024], rang[1024], uz[1024];
struct dreapta {int a, b, c;} d[1024];
struct punct { int x, y; } p[1024];
int multime(int x)
{
if( x!=reg[x]) reg[x]= multime( reg[x]);
return reg[x];
}
void reuneste(int i, int j)
{
i= multime(i);
j= multime(j);
if( rang[i] < rang[j])
reg[i]= reg[j];
else reg[j]= reg[i];
if( rang[i]== rang[j]) rang[i]++;
}
void solve()
{
for(int i=1; i<=m; ++i)
for(int j=1; j<=m; ++j) if( multime(i)!=multime(j)) {
int k=0;
while( ++k<=n && (d[k].a *p[i].x + d[k].b* p[i].y + d[k].c)*( d[k].a* p[j].x + d[k].b*p[j].y + d[k].c)>0 ) ;
if( k==n+1) reuneste(i, j);
}
}
void verif()
{
int nr=0;
for(int i=1; i<=m; ++i) if( !uz[ reg[i]]) {
uz[reg[i]]=1;
nr++;
}
freopen("regiuni.out","w",stdout);
printf("%d\n",nr);
}
void init()
{
for(int i=1; i<=m; ++i) reg[i]=i;
}
int main()
{
freopen("regiuni.in","r",stdin);
scanf("%d %d",&n, &m);
for(int i=1; i<=n; ++i) scanf("%d %d %d",&d[i].a, &d[i].b, &d[i].c);
for(int i=1; i<=m; ++i) scanf("%d %d",&p[i].x, &p[i].y);
init();
solve();
verif();
return 0;
}