Pagini recente » Cod sursa (job #2840575) | Cod sursa (job #337176) | Cod sursa (job #561128) | Cod sursa (job #1838743) | Cod sursa (job #38045)
Cod sursa(job #38045)
#include <cstdio>
struct dreapta { int a, b, c; };
struct punct { int x, y; };
const int NMAX = 1024;
int N, M;
dreapta D[NMAX];
punct P[NMAX];
bool beg[NMAX];
void read(void) {
FILE *fin = fopen("regiuni.in", "rt");
int i;
fscanf(fin, " %d %d", &N, &M);
for (i = 0; i < N; ++i)
fscanf(fin, " %d %d %d", &D[i].a, &D[i].b, &D[i].c);
for (i = 0; i < M; ++i)
fscanf(fin, " %d %d", &P[i].x, &P[i].y);
fclose(fin);
}
inline int semn(punct p, dreapta d) {
return d.a * p.x + d.b * p.y + d.c > 0 ? 1 : -1;
}
void partitie(int p, int r, dreapta d) {
int i = p, j = r, v;
punct aux;
v = semn(P[p], d);
while (i < j) {
do { ++i; } while ( i < j && semn(P[i], d) * v == -1);
do { --j; } while ( i < j && semn(P[j], d) * v == 1 );
if (i < j) {
aux = P[i]; P[i] = P[j]; P[j] = aux;
}
}
beg[i + 1] = true;
}
void sortam(void) {
int i, j, k;
beg[0] = true;
for (k = 0; k < N; ++k)
for (i = 0; i < M; i = j) {
for (j = i + 1; j < M && beg[j] == false; ++j);
partitie(i, j, D[k]);
}
}
void write(void) {
FILE *fout = fopen("regiuni.out", "wt");
int i, rez = 0;
for (i = 0; i < M; ++i)
if (beg[i]) ++rez;
fprintf(fout, "%d\n", rez);
fclose(fout);
}
int main() {
read();
sortam();
write();
return 0;
}