Pagini recente » Borderou de evaluare (job #1656879) | Cod sursa (job #40904)
Cod sursa(job #40904)
#include <cstdio>
#include <algorithm>
using namespace std;
#define Nmax 1001
#define a first
#define b second.first
#define c second.second
#define x first
#define y second
int n, m, ct;
pair<short, pair<short, short> > dr[Nmax];
pair<short, short> punct[Nmax];
unsigned int mat[Nmax][32], tmp[32];
void citire()
{
int i, p1, p2, p3;
scanf("%d %d\n", &n, &m);
for (i = 1; i <= n; ++i)
{
scanf("%d %d %d\n", &p1, &p2, &p3);
dr[i].a = p1;
dr[i].b = p2;
dr[i].c = p3;
}
for (i = 1; i <= m; ++i)
{
scanf("%d %d\n", &p1, &p2);
punct[i].x = p1;
punct[i].y = p2;
}
}
int cmp(int A, int B)
{
int i;
for (i = 0; i < 32; ++i)
if (mat[A][i] < mat[B][i])
return 1;
else if (mat[A][i] > mat[B][i])
return -1;
return 0;
}
void qsort(int st, int dr)
{
int i, j, sch;
i = st, j = dr;
sch = (st + dr) / 2;
do
{
while (cmp(i, sch) == 1)
++i;
while (cmp(sch, j) == 1)
--j;
if (i <= j)
{
memcpy(tmp, mat[i], sizeof(tmp));
memcpy(mat[i], mat[j], sizeof(tmp));
memcpy(mat[j], tmp, sizeof(tmp));
++i, --j;
}
}
while (i <= j);
if (st < j) qsort(st, j);
if (i < dr) qsort(i, dr);
}
void solve()
{
int i, j, k, ct = 0;
for (i = 1; i <= m; ++i)
{
k = -1;
for (j = 0; j < n; ++j)
{
if (j % 32 == 0)
++k;
if (dr[j + 1].a * punct[i].x + dr[j + 1].b * punct[i].y + dr[j + 1].c < 0)
mat[i][k] += 1 << (j % 32);
}
}
qsort(1, m);
ct = 1;
for (i = 2; i <= m; ++i)
if (cmp(i, i -1))
++ct;
printf("%d\n", ct);
}
int main()
{
freopen("regiuni.in", "r", stdin);
freopen("regiuni.out", "w", stdout);
citire();
solve();
return 0;
}