Pagini recente » Cod sursa (job #2325476) | Cod sursa (job #534508) | Cod sursa (job #3125487) | Cod sursa (job #2725719) | Cod sursa (job #55269)
Cod sursa(job #55269)
#include <fstream>
//#include <iostream>
//#include <math.h>
struct point {
int x,y;
};
struct line {
int a,b,c;
};
int n,m;
struct point p[1000];
struct line l[1000];
unsigned int a[1000][32];
float d(int a,int b,int c,int x,int y) {
/*float a2,b2,x1,y1,r;
std::cout << a << " " << b << " " << c << " " << x << " " << y << "\n";
if (a==0) {a2=1; b2=0;}
else
if ((x-y*(b/a))==0);
else {a2=(float)c/(x-y*(b/a)); b2=(float)-a2*(b/a);}
x1=(float)-c/(a+(a2-a)/(b2-b));
y1=(float)x1*(a2-a)/(b2-b);
r=sqrt((x1-x)*(x1-x)+(y1-y)*(y1-y));
if (((x1-x)<0&&(y1-y)>=0)||((x1-x)>=0&&(y1-y)<0)) r=-r;
std::cout << a2 << " " << b2 << " " << x1 << " " << y1 << " " << r << "\n";
return r;*/
if (b==0) {
if (y>0) return 1; else return -1;
} else {
float x2=1,y2,x3=10,y3,det;
y2=((float)-c-a*x2)/b;
y3=((float)-c-a*x3)/b;
det=(x2-x)*(y3-y)-(x3-x)*(y2-y);
if (det>0) return 1; else return -1;
}
}
void cutall() {
int i,j,k; int p1[1000],p1l,p2[1000],p2l;
for (i=0; i<m; i++) {
p1l=0; p2l=0;
for (j=0; j<n; j++)
if (d(l[i].a,l[i].b,l[i].c,p[j].x,p[j].y)>0)
p1[p1l++]=j;
else
p2[p2l++]=j;
for (j=0; j<p1l; j++)
for (k=0; k<p2l; k++)
a[p1[j]][p2[k]>>5]=a[p1[j]][p2[k]>>5]|(1<<(p2[k]%32))^(1<<(p2[k]%32));
//&=(0xffffffff-(1<<(p2[k]%32)));
}
}
int reg() {
int r=0,i,j,k,s[1000],p[1000],sl;
for (j=0; j<n; j++) s[j]=0;
for (i=0; i<n; i++) {
if (s[i]) continue;
else {
r++;
sl=1; p[0]=i;
k=0; s[i]=1;
while (k<sl) {
for (j=0; j<n; j++)
//if (s[j]) continue;
//else {
if (a[p[k]][j>>5]&(1<<(j%32))) {
p[sl++]=j;
s[j]=1;
}
//}
k++;
}
}
}
return r;
}
int main () {
std::ifstream fin ("regiuni.in");
std::ofstream fout ("regiuni.out");
int i; //for (i=0; i<1000; i++) an[i]=1000;
fin >> n >> m;
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();
//std::cout << "cutting graph\n";
cutall();
//std::cout << "counting regions\n";
i=reg();
//std::cout << i << "\n";
fout << i << "\n";
fout.close();
return 0;
}