Cod sursa(job #388047)

Utilizator taloibogdanTaloi Bogdan Cristian taloibogdan Data 29 ianuarie 2010 11:24:17
Problema Regiuni Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.26 kb
#include<stdio.h>
struct POINT{long x,y;}p[1005],p1;
struct lpd{long a,b,c;POINT p1,p2;}l[1005];
struct vtcn{long a,b;}a[1005];
long n,m,i,lng,j,n1,n0,f[1005],k,last;
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);
 lng=1;
 a[1].a=1;
 a[1].b=m;
 for(i=1;i<=n;++i)
    for(j=lng;j;--j)
        {n0=n1=0;
         for(k=a[j].a;k<=a[j].b;++k)
            if(ccw(l[i].p1,l[i].p2,p[k])<0)
              f[k]=0,++n0;
              else
              f[k]=1,++n1;
         last=a[j].b;
         for(k=a[j].a;k<=a[j].a+n0-1;++k)
            while(f[k]!=0){p1=p[k];p[k]=p[last];p[last--]=p1;}
         if(n0*n1)a[++lng].b=a[j].b,a[j].b=a[j].a+n0-1,a[lng].a=a[j].a+n0;}
 printf("%ld\n",lng);
 return 0;
}