Pagini recente » Cod sursa (job #2087323) | Cod sursa (job #286186)
Cod sursa(job #286186)
#include <cstdio>
#include <vector>
#include <cstdlib>
#include <ctime>
#define maxN 1024
using namespace std;
short int A[maxN], B[maxN], C[maxN], X[maxN], Y[maxN], shuffle[maxN], N, M, NrGrupe = 1;
vector <short int> Grupe[maxN];
int ask (int dr, int i) {
return (A[dr] * X[i] + B[dr] * Y[i] + C[dr]);
}
void baga_marfa (int dr) {
int i, j, Nr = NrGrupe;
vector <short int> now1, now2;
for (i = 1; i <= Nr; ++ i) {
now1.clear();
now2.clear();
for (j = 0; j < Grupe[i].size(); ++ j)
if (ask(dr, Grupe[i][j]) < 0)
now1.push_back(Grupe[i][j]);
else
now2.push_back(Grupe[i][j]);
if (now1.size ()) {
Grupe[i].resize(now1.size());
Grupe[i] = now1;
if (now2.size()) {
Grupe[ ++ NrGrupe].resize(now2.size());
Grupe[ NrGrupe] = now2;
}
} else {
Grupe[i].resize(now2.size());
Grupe[i] = now2;
}
}
}
void random_shuffle () {
int i, x, y;
short int aux;
srand(time(NULL));
for (i = 1; i <= N; ++ i) shuffle[i] = i;
for (i = 1; i <= 3000; ++ i) {
x = rand () % N + 1;
y = rand () % N + 1;
aux = shuffle[x];
shuffle[x] = shuffle[y];
shuffle[y] = aux;
}
}
int main () {
int i;
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", &X[i], &Y[i]);
Grupe[1].push_back(i);
}
random_shuffle();
for (i = 1; i <= N; ++ i)
baga_marfa(shuffle[i]);
printf("%d\n", NrGrupe);
}