Cod sursa(job #40419)

Utilizator damaDamaschin Mihai dama Data 27 martie 2007 13:52:31
Problema Regiuni Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.11 kb
#include <stdio.h>
#include <vector>
#include <algorithm>
using namespace std;

struct line
{
       int a, b, c;
};
struct point
{
       int x, y, reg;
};


int n, m, sol;
line l[1001];
point v[1001];


bool cmp(point one, point two)
{
     return one.reg < two.reg;
}
int f(int i, int j);

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

    int i, j, cnt = 1;
    
    scanf("%d%d", &n, &m);
    for(i = 1; i <= n; ++i)
    {
          scanf("%d%d%d", &l[i].a, &l[i].b, &l[i].c);
    }
    for(i = 1; i <= m; ++i)
    {
          scanf("%d%d", &v[i].x, &v[i].y);
    } 
    
    for(i = 1; i <= n; ++i)
    {
          for(j = 1; j <= m;)
          {
                while(v[j].reg == v[j + 1].reg && j <= m)
                {
                             if(f(i, j) > 0)
                             {
                                     v[j].reg = cnt;
                             }
                             ++j;
                }
                if(f(i, j) > 0)
                        v[j].reg = cnt;
                ++j;
                ++cnt;
          }
          
          sort(v + 1, v + m + 1, cmp);
          /*
          for(j = 1; j <= m; ++j)
          {
                printf("%d %d %d\n", v[j].x, v[j].y, v[j].reg);
          }
          printf("\n");
          */
    }
    
    for(i = 1; i <= m; ++i)
    {
          if(v[i].reg != v[i - 1].reg)
                  ++ sol;
    }
    printf("%d\n", sol);
    
    return 0;
}

int f(int i, int j)
{
    int x1, x2, y1, y2;
    if(l[i].a == 0)
    {
              x1 = 1;
              x2 = 2;
              y1 = -l[i].c / l[i].b;
              y2 = -l[i].c / l[i].b;
    }
    else if(l[i].b == 0)
    {
              x1 = -l[i].c / l[i].a;
              x2 - -l[i].c / l[i].a;
              y1 = 1;
              y2 = 2;
    }
    else
    {
        x1 = 0;
        y1 = -l[i].c / l[i].b;
        x2 = -l[i].c / l[i].a;
        y2 = 0;
    }
    return x1 * y2 + x2 * v[j].y + v[j].x * y1 - x1 * v[j].y - y1 * x2 - y2 * v[j].x;
}