Cod sursa(job #51287)

Utilizator hvm2hvmvoicu hodrea hvm2hvm Data 10 aprilie 2007 19:50:03
Problema Regiuni Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.39 kb
#include <fstream>
//#include <iostream>

struct line {
   int a,b,c;
};

struct point {
   int x,y;
};

struct line l[1000];
struct point p[1000];
int m,n;
int rp[1000],r[1000],nr=0;

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;
   if (tmp<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;
}