Cod sursa(job #55269)

Utilizator hvm2hvmvoicu hodrea hvm2hvm Data 26 aprilie 2007 21:20:13
Problema Regiuni Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.37 kb
#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;
}