Pagini recente » Cod sursa (job #2270777) | Cod sursa (job #1378222) | Cod sursa (job #1031964) | Cod sursa (job #35272) | Cod sursa (job #2628574)
#include <bits/stdc++.h>
#define maxn 1005
#define ld long double
std::ifstream fin ("regiuni.in");
std::ofstream fout ("regiuni.out");
struct Line{
int a, b, c;
}line[maxn];
struct Point{
int x, y;
}point[maxn];
bool mat[maxn][maxn];
ld det (ld x1, ld y1, ld x2, ld y2, ld x3, ld y3){
return (x3-x1) * (y2-y1) - (x2-x1) * (y3-y1);
}
void radixSort (int L, int P, int *order){
std::vector <int> v[2];
int i, j, l, p, crt;
for (l=0; l<L; l++){
v[0].clear();
v[1].clear();
for (i=0; i<P; i++){
crt = order[i];
v[mat[crt][l]].push_back (crt);
}
for (i=0, j=0; i<v[0].size(); i++, j++)
order[j] = v[0][i];
for (i=0; i<v[1].size(); i++, j++)
order[j] = v[1][i];
}
}
bool compare (int L, bool *a, bool *b){
for (int i=0; i<L; i++)
if (a[i] != b[i])
return 0;
return 1;
}
int main()
{
int L, P, i, j;
fin >> L >> P;
for (i=0; i<L; i++)
fin >> line[i].a >> line[i].b >> line[i].c;
for (i=0; i<P; i++)
fin >> point[i].x >> point[i].y;
long double x1, x2, y1, y2, a, b, c;
for (int l=0; l<L; l++){
a = line[l].a;
b = line[l].b;
c = line[l].c;
if (a == 0){
x1 = 0;
x2 = 1;
y1 = y2 = (long double)1.0* (-c) / (b);
}
else if (b == 0){
y1 = 0;
y2 = 1;
x1 = x2 = (long double)1.0* (-c) / (a);
}
else{
x1 = 0;
y1 = (long double)(1.0 * (-c) - a*x1) / b;
x2 = 1;
y2 = (long double)(1.0 * (-c) - a*x2) / b;
}
if (a*x1+b*y1+c != 0)
std::cout << "incorect";
if (a*x2+b*y2+c != 0)
std::cout << "incorect";
for (int p=0; p<P; p++){
if (det (x1, y1, x2, y2, point[p].x, point[p].y) > 0)
mat[p][l] = true;
else
mat[p][l] = false;
}
}
/*
for (i=0; i<P; i++, fout << '\n')
for (j=0; j<L; j++)
fout << mat[i][j] << ' ';
*/
int order[maxn];
for (i=0; i<P; i++)
order[i] = i;
radixSort (L, P, order);
//fout <<"\n\n\n";
/*
for (i=0; i<P; i++, fout << '\n')
for (j=0; j<L; j++)
fout << mat[order[i]][j] << ' ';
*/
int ans = 1;
for (i=1; i<P; i++){
if (compare(L, mat[order[i]], mat[order[i-1]]) == false)
ans ++;
}
fout << ans << '\n';
return 0;
}