Cod sursa(job #46832)

Utilizator Bluedrop_demonPandia Gheorghe Bluedrop_demon Data 3 aprilie 2007 00:34:07
Problema Poligon Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.71 kb
// Problema poligon
// :D Hai ca sunt increzator :D

#include <stdio.h>
#define MAX       801

long P[MAX][2];

long X = -2, Y = -3;

int Int( long xm, long ym, long x1, long y1, long x2, long y2 )
{
    float m1, n1, m2, n2, yt, xt;
    long YM, Ym, XM, Xm;
    if( x1 == x2 )
        {
              if( y2 > y1 ) { YM = y2; Ym = y1; } else { YM = y1; Ym = y2; }
              if( ( xm == x1 ) && ( ym >= Ym ) && (ym <= YM ) ) return 2;
              m1 = (ym - Y)/(xm - X);
              n1 = (Y*xm - ym*X)/(xm - X);
              yt = m1*x1 + n1;
              if( ( xm > x1 ) && ( yt >= Ym ) && ( yt <= YM ) ) return 1;
        }
        else
        {
            m2 = (y1 - y2)/(x1 - x2);
            n2 = (y2*x1 - y1*x2)/(x1 - x2);
            yt = m2*xm + n2;
            if( ym == yt ) return 2;
            m1 = (ym - Y)/(xm - X);
            n1 = (Y*xm - ym*X)/(xm - X);
            if( m1 == m2 ) return 0;
            xt = (n2 - n1)/(m1 - m2);
            yt = (m1*n2 - m2*n1)/(m1 - m2);
            if( ( xt <= X ) || ( xt > xm ) || ( yt <= Y ) || ( yt > ym ) )  return 0;
            if( y2 > y1 ) { YM = y2; Ym = y1; } else { YM = y1; Ym = y2; }
            if( x2 > x1 ) { XM = x2; Xm = x1; } else { XM = x1; Xm = x2; }
            if( ( xt < Xm ) || ( xt > XM ) || ( yt < Ym ) || ( yt > YM ) )  return 0;
            return 1;
        }
    return 0;
}

int main()
{
    int n, i;
    long m;
    int cd;
    long nr, nrp = 0;
    long x, y;   
    freopen( "poligon.in" ,"rt", stdin );
             scanf( "%d %ld", &n, &m );
             for( i=1; i<=n; i++ ) scanf( "%ld %ld", &P[i][0], &P[i][1] );
             while( m )
                    {
                             m--;
                             scanf( "%ld %ld", &x, &y );
                             nr = 0;
                             for( i=1; i<n; i++ )
                                  {
                                       cd = Int( x, y, P[i][0], P[i][1], P[i+1][0], P[i+1][1] );
                                       if( cd == 2 ) { nrp++; break; }
                                           else if( cd == 1 ) nr++;
                                  }
                             if( cd != 2 )
                             {
                                 cd = Int( x, y, P[1][0], P[1][1], P[n][0], P[n][1] );
                                 if( cd == 2 ) nrp++; else if( cd == 1 ) nr++;
                             }
                             if( ( cd != 2 ) && ( nr%2 == 1 ) ) nrp++; 
                    }                             
    fclose( stdin );
    
    
    freopen( "poligon.out", "wt", stdout );
             printf( "%ld\n", nrp );
    fclose( stdout );
    return 0;
}