Cod sursa(job #51291)
#include <fstream>
#include <iostream>
#pragma option -Os
struct line {
int a,b,c;
};
struct point {
int x,y;
};
struct line l[1000];
struct point p[1000];
int rp[1000],r[1000],nr=0;
int m,n;
int side(int x1,int y1,float x2,float y2,float x3,float y3) {
float tmp=(float)(x2-x1)*(y3-y1)-(x3-x1)*(y2-y1);
if (tmp>0) return 1;
if (tmp==0) return 0;
return -1;
}
int main () {
std::ifstream fin("regiuni.in");
std::ofstream fout ("regiuni.out");
int i,j;
for (i=0; i<1000; i++) rp[i]=0;
float x1,x2,y1,y2;
fin >> m >> n;
for (i=0; i<m; i++)
fin >> l[i].a >> l[i].b >> l[i].c;
for (i=0; i<n; i++)
fin >> p[i].x >> p[i].y;
fin.close();
x1=1; x2=10;
for (i=0; i<m; i++) {
if (l[i].b==0) {
x1=-l[i].c/l[i].a; x2=-l[i].c/l[i].a;
y1=1; y2=10;
} else {
x1=1; x2=10;
y1=(-l[i].c-l[i].a*x1)/l[i].b;
y2=(-l[i].c-l[i].a*x2)/l[i].b;
}
for (j=0; j<nr; j++) r[j]=0;
for (j=0; j<n; j++)
if (side(p[j].x,p[j].y,x1,y1,x2,y2)==-1) {
if (r[rp[j]]==0) {
r[rp[j]]=nr;
rp[j]=nr;
nr++;
} else {
rp[j]=r[rp[j]];
}
}
for (j=0; j<n; j++)
std::cout << rp[j] << " ";
std::cout << "\n";
}
std::cout << nr << "\n";
fout << nr << "\n";
fout.close();
return 0;
}