Cod sursa(job #40073)

Utilizator mariusdrgdragus marius mariusdrg Data 27 martie 2007 11:06:29
Problema Regiuni Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.86 kb
#include<stdio.h>
#include<algorithm>

using namespace std;

const int maxn = 1001;

int i;
int n;
int j;
int nrd, nrp;
int a[maxn], b[maxn], c[maxn];
int x[maxn], y[maxn];
int mat[maxn][maxn];
int ind[maxn];
int nr;


double calca(double x1,double y1,double x2,double y2, double x3,double y3)
{
        return x1 * y2 + x2 * y3 + x3 * y1 - y1 * x2 - y2 * x3 - y3 * x1;
}

bool cmpf(const int i,const int j)
{
        int x;
        for(x = 1;x <= nrd; ++x)
        {
                if (mat[i][x] < mat[j][x]) return true;
                if (mat[i][x] > mat[j][x]) return false;
        }
        
        return false;
}

bool egal(int i, int j)
{
        int x;
        for(x = 1;x <= nrd; ++x)
        {
                if (mat[i][x] != mat[j][x]) return false;
        }
        return true;;
}

int main()
{
        freopen("regiuni.in","r",stdin);
        freopen("regiuni.out","w",stdout);
        scanf("%d %d",&nrd,&nrp);
        for(i = 1;i <= nrd; ++i)
        {
                scanf("%d %d %d",&a[i],&b[i],&c[i]);
        }
        for(i = 1;i <= nrp; ++i)
        {
                scanf("%d %d",&x[i],&y[i]);
                ind[i] = i;
                
        }
        for(i = 1;i <= nrd; ++i)
        {
                double x1 = 1;
                double y1 = (-c[i] - a[i] * x1) / b[i];
                double x2 = -1;
                double y2 = (-c[i] - a[i] * x2) / b[i];
                for(j = 1;j <= nrp; ++j)
                {
                        mat[j][i] = -1;
                        if (calca(x1,y1,x2,y2,x[j],y[j]) < 0) mat[j][i] = 1;
                        if (calca(x1,y1,x2,y2,x[j],y[j]) > 0) mat[j][i] = 0;

                }
        }
        sort(ind + 1,ind + nrp + 1, cmpf);

        for(i = 1;i <= nrp; ++i)
        {
                if (!egal(ind[i],ind[i - 1]))nr++;
        }
        nr++;
        printf("%d\n",nr);
        
        return 0;
}