Cod sursa(job #402488)

Utilizator MarcvsHdrMihai Leonte MarcvsHdr Data 23 februarie 2010 21:37:52
Problema Poligon Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 5.5 kb
# include <stdio.h>
# include <stdlib.h>

# define MAXN 800
# define MAXC 60000

typedef struct PUNCT{
        long int x,y;
        } PUNCT;
        
typedef struct SEGMENT{
        PUNCT a,b;
        } SEGMENT;
        
typedef struct NOD{
        SEGMENT seg;
        NOD *next;
        } NOD;
        
typedef struct LISTA{
        NOD *begin,*end;
        } LISTA;
              
void add(SEGMENT seg, LISTA &l)
{
     NOD *p=(NOD*) malloc (sizeof(NOD));
     p->next=NULL;
     p->seg=seg;
     if (l.begin==NULL)
        {
        l.begin=p;
        l.end=p;
        }
     else
         {
         l.end->next=p;
         l.end=p;
         }
}
        
PUNCT p[MAXN+2];
PUNCT crime[MAXC+1];
long int n,m;
long int event[MAXN+1],nevent;
LISTA    eventsegments[MAXN+1]={{0,0}},eventlinesegments[MAXN+2]={{0,0}};

void citire()
{
     FILE *f=fopen("poligon.in","r");
     fscanf(f,"%ld%ld",&n,&m);
     long int i;
     for (i=1;i<=n;i++)
         fscanf(f,"%ld%ld",&p[i].x,&p[i].y);
     p[n+1]=p[1];
     p[0]=p[n];
     for (i=1;i<=m;i++)
         fscanf(f,"%ld%ld",&crime[i].x,&crime[i].y);
     fclose(f);
}

int compara_inturi(const void *a, const void *b)
{
    return *((long int *)a)-*((long int *)b);
}

int is_transitioning(long int i)
{
    if ((p[i-1].y-p[i].y)*(p[i+1].y-p[i].y)<=0) return 1;
    return 0;
}

void initializeaza()
{
     long int i,j;
     //impartim planul in benzi conform cu coordonatele "y" ale punctelor
     for (i=1;i<=n;i++)
         event[i]=p[i].y;
     qsort(event+1,n,sizeof(long int),compara_inturi);
     long int skipped=0;
     for (i=2;i<=n;i++)
         if (event[i]==event[i-1]) skipped++;
         else event[i-skipped]=event[i];
     nevent=n-skipped;
     //acum alocam la interval dintre doua evenimente cate o lista de segmente
     SEGMENT seg;
     PUNCT pct;
     for (j=1;j<=n;j++)
         {
         seg.a=p[j];
         seg.b=p[j+1];
         if (seg.a.y>seg.b.y)
            {
            pct=seg.a;
            seg.a=seg.b;
            seg.b=pct;
            }
         //cautam listele de benzi de evenimente in care trebuie sa introducem segmentul
         for (i=1;i<=nevent-1;i++)
             if (seg.a.y<event[i+1]||seg.b.y>event[i])
                add(seg,eventsegments[i]);
         //cautam si listele cu evenimentele in care trebuie sa adaugam segmentul (inseamna ca segmentul le contine in interior)
         for (i=1;i<=nevent;i++)
             if (seg.a.y<event[i]&&seg.b.y>event[i])
                add(seg,eventlinesegments[i]);
         }
     //intainte de a termina, trebuie sa mai adaugam in listele cu evenimentele si segmente formate din alte evenimente
     for (j=1;j<=n;j++)
         {
         seg.a=p[j];
         seg.a.y--;
         seg.b=p[j];
         seg.b.y++;
         //trebuie sa cautam listele de evenimente in care sa introducem segmentul, dar doaca evenimentul este tranzitoriu
         if (is_transitioning(j))
         for (i=1;i<nevent;i++)
             if (p[j].y==event[i])
                add(seg,eventlinesegments[i]);
         }
     // se mai pune acum problema punctelor care sunt coliniare cu evenimentele, dar pe aia o vom trata separat
}

long int binsearcheventband(long int key)
// Conditia de oprire este ca punctul sa fie cuprins intre
// doua coordonate diferite event[i],event[i+1]
{
        if (event[1]>key || event[nevent]<key) return 0;
        long int m,li=1,lf=nevent-1;
        while (li<=lf)
              {
              m=(li+lf)/2;
              if (event[m]<key&&event[m+1]>key) return m;
              else if (event[m]>key) lf=m-1;
              else li=m+1;
              }
        return -1;
}

long int binsearcheventline(long int key)
{
     if (event[1]>key||event[nevent]<key) return 0;
     long int m,li=1,lf=nevent;
     while (li<=lf)
           {
           m=(li+lf)/2;
           if (event[m]==key) return m;
           if (event[m]>key)  lf=m-1;
           else li=m+1;
           }
     return -1;
}

long int get_arie(PUNCT a, PUNCT b, PUNCT c)
{
     return (a.x-c.x)*(b.y-c.y)-(b.x-c.x)*(a.y-c.y);
}

long int count_to_left(PUNCT pct, LISTA l)
{
     NOD *p=l.begin;
     long int arie,sol=0;
     while (p)
           {
           arie = get_arie(p->seg.a,p->seg.b,pct);
           if (arie==0) return 1;
           if (arie>0)  sol++;
           p=p->next;
           }
     return sol;
}

long int is_inside(PUNCT p)
{
     long int eventband,eventline;
     eventband = binsearcheventband(p.y);
     if (eventband==0) return 0; // inseamna ca este mai jos/sus de poligon
     long int totheleft;
     if (eventband!=-1) 
        {
        totheleft = count_to_left(p,eventsegments[eventband]);
        }
     else
         {
         eventline = binsearcheventline(p.y);
         if (eventline==-1) printf("Fatal error???");
         totheleft = count_to_left(p,eventlinesegments[eventline]);
         }
     return totheleft&1;
}

long int calculeaza()
{
     long int i,sol=0;
     for (i=1;i<=m;i++)
         if (is_inside(crime[i])) 
            {
            sol++;
            //printf("%ld %ld\n",crime[i].x,crime[i].y);                     //AICI!!!
            }
     return sol;
}

void scrie(long int sol)
{
     FILE *g=fopen("poligon.out","w");
     fprintf(g,"%ld\n",sol);
     fclose(g);
}

int main()
{
    citire();
    initializeaza();
    long int sol=calculeaza();
    scrie(sol);
    //fflush(stdin);
    //getchar();
    return 0;
}