Cod sursa(job #387987)

Utilizator taloibogdanTaloi Bogdan Cristian taloibogdan Data 28 ianuarie 2010 22:18:58
Problema Regiuni Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.65 kb
#include<stdio.h>
struct POINT{long x,y;}p[1005],p1,p2;
struct lpd{long a,b,c;POINT p1,p2;}l[1005];
struct nod{long x;nod *next;}*e,*k;
struct vtcn{nod *b,*e;}a[1005];
long n,m,i,lng,j,f;
void inserare_end(long x,long y)
{nod *aux;
 aux=new nod;
 aux->x=x;
 aux->next=NULL;
 a[y].e->next=aux;
 a[y].e=aux;
 if(a[y].b==NULL)a[y].b=a[y].e;}
long ccw(POINT A,POINT B,POINT C)
{
long p;
p=(B.x-A.x)*(C.y-B.y)-(B.y-A.y)*(C.x-B.x);
if(p==0)return 0;
if(p>=0)return  1;
return -1;
}

int main()
{
 freopen("regiuni.in","r",stdin);
 freopen("regiuni.out","w",stdout);
 scanf("%ld%ld",&n,&m);
 for(i=1;i<=n;++i)
    {scanf("%ld%ld%ld",&l[i].a,&l[i].b,&l[i].c);
     if(l[i].b==0)l[i].p1.x=(-l[i].c)/l[i].a,l[i].p1.y=1;
     else
     l[i].p1.y=(-l[i].c)/l[i].b,l[i].p1.x=0;
     if(l[i].a==0)l[i].p2.y=(-l[i].c)/l[i].b,l[i].p2.x=1;
     else
     l[i].p2.x=(-l[i].c)/l[i].a,l[i].p2.y=0;}
 for(i=1;i<=m;++i)
    {scanf("%ld%ld",&p[i].x,&p[i].y);
     inserare_end(i,1);}
 lng=1;
 for(i=1;i<=n;++i)
    for(j=lng;j;--j)
       {a[j].e=NULL;
        for(k=a[j].b;k->next!=NULL;)
           {p1=l[i].p1;
            p2=l[i].p2;
            if(ccw(p1,p2,p[k->x])<0)f=1;
            else f=0;
            if(f)
            {e=k;
             k=k->next;
             if(e==a[j].b)a[j].b=NULL;
             inserare_end(e->x,j);
             delete e;}
             else
            {e=k;
             k=k->next;
             inserare_end(e->x,lng+1);
             delete e;}}
        if(a[j].b==NULL)a[j].b=a[lng+1].b,a[j].e=a[lng+1].e,a[lng+1].b=NULL,a[lng+1].e=NULL;
        if(a[lng+1].b!=NULL)++lng;}
 printf("%ld\n",lng);
 return 0;
}