Cod sursa(job #1150349)

Utilizator marta_diannaFII Filimon Marta Diana marta_dianna Data 22 martie 2014 21:31:23
Problema Regiuni Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.82 kb
#include<fstream>
#define NMAX 1010

using namespace std;

ifstream f("regiuni.in");
ofstream g("regiuni.out");

struct punct
{
    int x, y;
    punct *urm;
}*a[NMAX];
struct dreapta
{
    int a, b, c;
}ec[NMAX];
int n, m, nr=1;

void Citeste()
{
    int i, j;
    punct *q, *ultim;
    f>>n>>m;
    for (i=1; i<=n; ++i) f>>ec[i].a>>ec[i].b>>ec[i].c;
    a[1]=ultim=new punct; a[1]->urm=NULL;
    f>>a[1]->x>>a[1]->y;
    for (j=2; j<=m; ++j)
    {
        q=new punct; q->urm=NULL;
        f>>q->x>>q->y;
        ultim->urm=q; ultim=q;
    }
}

void Solve()
{
    int i, j, sg;
    punct *q, *p1=NULL, *u1=NULL, *p2=NULL, *u2=NULL, *cr, *urm;

    for (i=1; i<=n; ++i)
    {
        p1=p2=u1=u2=NULL;
        for (j=1; j<=nr; ++j)
        {
            cr=a[j];

            while (cr!=NULL)
            {
                urm=cr->urm;
                cr->urm=NULL;

                sg=ec[i].a*cr->x+ec[i].b*cr->y+ec[i].c;

                if (sg<0)
                {
                    if (p1==NULL) p1=u1=cr;
                    else
                    {
                        u1->urm=cr;
                        u1=cr;
                    }

                }
                else
                {
                    if (p2==NULL) p2=u2=cr;
                    else
                    {
                        u2->urm=cr;
                        u2=cr;
                    }
                }
                cr=urm;
            }
        }
        if (p1!=NULL && p2!=NULL)
            {
                a[j]=p1;
                a[++nr]=p2;
            }
            else
                if (p1!=NULL) a[j]=p1;
                else a[j]=p2;

    }
    g<<nr<<"\n";
}
int main()
{
    Citeste();
    Solve();
    f.close();
    g.close();
    return 0;
}