Cod sursa(job #38899)

Utilizator crawlerPuni Andrei Paul crawler Data 26 martie 2007 11:18:55
Problema Regiuni Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.3 kb
#include <stdio.h>
#include <bitset>
#include <vector>

using namespace std;

struct dreapta
 {
  int a,b,c;
 } d[1001];

struct pct
 {
  int x,y;
 } p[1001];

 
int m, S;
char e[1001];

int main()
 {
  freopen("regiuni.in","r",stdin);
  freopen("regiuni.out","w",stdout);

  int i,j,n,aux,k,a1,a2;

  scanf("%d%d", &n,&m);

  for(i=1;i<=n;++i)
   scanf("%d%d%d", &d[i].a, &d[i].b, &d[i].c);

  for(i=1;i<=m;++i)
   scanf("%d%d", &p[i].x, &p[i].y);

  ++S;

  for(i=1;i<=m;++i)
   e[i] = S;


  for(j=1;j<=n;++j)
  for(i=1;i<=m;++i)
   {
    aux = e[i];
    vector <int> a;
    a.clear();

    a1 = 0;
    a2 = 0;

    for(k=i;e[k] == aux;++k)
     if(d[j].a*p[k].x+d[j].b*p[k].y+d[j].c < 0)
      {
       a.push_back(k);
       ++a1;
      }
       else
      ++a2;

    i = k;

    if(a1 > 0)
     if(a2 > 0)
    if(a.size())
     {
      for(k=i;e[k] == aux;++k)
       if(d[j].a*p[k].x+d[j].b*p[k].y+d[j].c < 0)
        e[k] = S;

      ++S;

      int last = i;
      for(k=0;k<a.size();++k)
       if(a[k] != last)
        {
         while(e[last] == S-1)
          ++last;
         swap(p[a[k]],p[last]);
         swap(e[a[k]],e[last]);
        }
         else
        ++last;
     }

   }

  printf("%d\n", S);

  return 0;
 }