Pagini recente » Cod sursa (job #2881911) | Cod sursa (job #1955592) | Cod sursa (job #619160) | Cod sursa (job #537756) | Cod sursa (job #38088)
Cod sursa(job #38088)
#include <stdio.h>
#include <set>
using namespace std;
#define in "regiuni.in"
#define out "regiuni.out"
#define dim 1001
int n, m;
struct punct { int x, y; } p[dim];
struct dreapta { int a, b, c; } d[dim];
int sel[dim];
set<int> total;
int Ok(punct A, punct B);
int main()
{
int f,g,h;
int q[4];
int next, minus;
int j;
int aux=0;
//freopen(in,"r",stdin);
FILE *fin = fopen(in,"r");
freopen(out,"w",stdout);
fscanf(fin,"%d%d", &n, &m);
fscanf(fin,"\n");
char linie[21];
for ( int i = 1; i <= n; i++ )
{
//scanf("%d%d%d", &f, &g, &h);
fgets(linie,20,fin);
j = 0;
minus = 1;
next = 0;
aux = 0;
while ( linie[j] != '\n' )
{
if ( linie[j] == ' ' )
{
next += 1;
q[next] = minus*aux;
aux = 0;
minus = 1;
}
else
{
if ( linie[j] == '-' ) minus = -1;
else aux *= 10, aux += (int)linie[j]-48;
}
j++;
}
d[i].a = q[1];
d[i].b = q[2];
d[i].c = minus*aux;
}
for ( int i = 1; i <= m; i++ )
{
fgets(linie,20,fin);
j = 0;
minus = 1;
next = 0;
aux = 0;
while ( linie[j] != '\n' )
{
if ( linie[j] == ' ' )
{
next += 1;
q[next] = minus*aux;
aux = 0;
minus = 1;
}
else
{
if ( linie[j] == '-' ) minus = -1;
else aux *= 10, aux += (int)linie[j]-48;
}
j++;
}
p[i].x = q[1];
p[i].y = aux*minus;
}
for ( int i = 1; i < m; i++ )
{
if ( sel[i] > 0 ) continue;
for ( int j = i+1; j <= m; j++ )
{
if ( Ok(p[i],p[j]) ) sel[j] = i, sel[i] = i;
}
if ( !sel[i] ) sel[i] = i;
}
if ( !sel[m] ) sel[m] = m;
for ( int i = 1; i <= m; i++ )
{
// printf("%d ", sel[i]);
int k = sel[i];
total.insert(k);
}
printf("%d",total.size());
}
int Ok(punct A, punct B)
{
int v1, v2;
for ( int i = 1; i <= n; i++ )
{
if ( d[i].a*A.x + d[i].b*A.y + d[i].c <= 0 ) v1 = -1;
else v1 = 1;
if ( d[i].a*B.x + d[i].b*B.y + d[i].c <= 0 ) v2 = -1;
else v2 = 1;
if ( v1 != v2 ) return 0;
}
return 1;
}