Cod sursa(job #386081)

Utilizator remusmpRemus MP remusmp Data 23 ianuarie 2010 23:41:00
Problema Poligon Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.93 kb
#include <stdio.h>

int sgn(int a)
{
    if (a<0) return -1;
    else
        if (a>0) return 1;
        else
        return 0;
}

int main()
{
    FILE* fin = fopen("poligon.in", "r");
    FILE* fout = fopen("poligon.out", "w");
    
    int N, M;
    fscanf(fin, "%d %d", &N, &M);
    
    int POL[802][2];
    int INF[60002][2];
    for (int i = 1; i <= N; i++)
    {
        fscanf(fin, "%d %d", &POL[i][0], &POL[i][1]);
    }
    
    POL[N+1][0] = POL[1][0];
    POL[N+1][1] = POL[1][1];
    POL[0][0] = POL[N][0];
    POL[0][1] = POL[N][1];
    
    for (int i = 0; i < M; i++)
    {
        fscanf(fin, "%d %d", &INF[i][0], &INF[i][1]);
    }
    
    int valid = 0;
    for (int i = 0; i < M; i++)
    {
        int ct = 0;
        for (int j = 1; j <= N; j++)
        {
            if (POL[j][0] >= INF[i][0] && POL[j-1][0] >= INF[i][0])
            {
                           if ((POL[j][1] > INF[i][1] && POL[j-1][1] < INF[i][1]) || (POL[j][1] < INF[i][1] && POL[j-1][1] > INF[i][1]))
                           {
                                          ct++;                                       
                           }
                           else
                           {
                              if (INF[i][1] == POL[j][1])
                              {
                                            int idx1 = j-1;
                                            if (INF[i][1] == POL[idx1][1])
                                               idx1--;
                                            int idx2 = j+1;
                                            if (INF[i][1] == POL[idx2][1])
                                               idx2++;
                                            
                                            if (sgn(POL[idx1][1] - INF[i][1]) != sgn(POL[idx2][1] - INF[i][1]))
                                               ct++;
                              }
                               
                           }
            }
            else
            {
                if ((POL[j][0] > INF[i][0] && POL[j-1][0] < INF[i][0]) || (POL[j][0] < INF[i][0] && POL[j-1][0] > INF[i][0]))
                {
                   
                           if ((POL[j][1] > INF[i][1] && POL[j-1][1] < INF[i][1]) || (POL[j][1] < INF[i][1] && POL[j-1][1] > INF[i][1]))
                           {
                                          ct++;                                       
                           }
                           else
                           {
                               if (POL[j-1][1] == INF[i][1] && POL[j][1] == INF[i][1])
                                  ct++;
                           }
                }
            }
        }
        
        if (ct % 2 != 0)
        {
               valid++;
        }
    }
    
    fprintf(fout, "%d", valid);
    fclose(fin);
    fclose(fout);
    
    return 0;
}