Pagini recente » Cod sursa (job #1698894) | Cod sursa (job #711238) | Cod sursa (job #2044219) | Cod sursa (job #236128) | Cod sursa (job #38087)
Cod sursa(job #38087)
#include <stdio.h>
#define NMAX 1010
int N, M;
int a[NMAX];
int b[NMAX];
int c[NMAX];
int xx[NMAX];
int yy[NMAX];
int pct[NMAX];
int nrg;
int beg[NMAX];
int end[NMAX];
int smn[NMAX];
inline int semn(int x, int y, int a, int b, int c)
{
if (x * a + y * b + c < 0) return -1;
return 1;
}
inline void SWAP(int &a, int &b)
{
int aux = a;
a = b;
b = aux;
}
void desparte(int beg, int end, int a, int b, int c, int gr)
{
int i, j, nr0 = 0, nr1 = 0, q;
for (i = beg; i <= end; i++) {
q = semn(xx[ pct[i] ], yy[ pct[i] ], a, b, c);
if (q < 0) nr0++;
else nr1++;
smn[i] = q;
}
if (!nr0 || !nr1) return;
nrg++;
::beg[gr] = ::beg[gr];
::beg[nrg] = ::beg[gr] + nr0;
::end[nrg] = ::end[gr];
::end[gr] = ::beg[gr] + nr0 - 1;
j = 1;
for (i = beg; i <= end; i++) {
if (smn[i] == 1) {
for (; j <= end && (smn[j] == 1 || j <= i); j++);
if (j <= end) { SWAP(pct[i], pct[j]); SWAP(smn[i], smn[j]); }
}
}
}
int main()
{
int i, j, q;
freopen("regiuni.in", "r", stdin);
freopen("regiuni.out", "w", stdout);
scanf("%d %d", &N, &M);
for (i = 1; i <= N; i++) scanf("%d %d %d", &a[i], &b[i], &c[i]);
for (i = 1; i <= M; i++) scanf("%d %d", &xx[i], &yy[i]);
for (i = 1; i <= M; i++) pct[i] = i;
nrg = 1;
beg[1] = 1; end[1] = M;
for (i = 1; i <= M; i++) {
q = nrg;
for (j = 1; j <= q; j++) desparte(beg[j], end[j], a[i], b[i], c[i], j);
}
printf("%d\n", nrg);
fclose(stdin);
fclose(stdout);
return 0;
}