Cod sursa(job #858265)

Utilizator andreii1Ilie Andrei andreii1 Data 18 ianuarie 2013 18:56:37
Problema Poligon Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.27 kb
#include <cstdio>

using namespace std;

struct punct{int x;int y;};

punct a[801],c;
int n,m,i,cnt;

int coliniaritate(punct c,punct a,punct b)
{
    if((a.x-c.x)*(a.y-b.y)!=(a.x-b.x)*(a.y-c.y))return 0;
    else
    if((a.x-c.x)*(b.x-c.x)<=0&&(a.y-c.y)*(b.y-c.y)<=0) return 1;
    return 0;
}

int sol(punct c, punct a, punct b)
{
    if(a.x>b.x) return((a.x-b.x)*a.y-(a.y-b.y)*(a.x-c.x)>=c.y*(a.x-b.x));
    else
    if(a.x<b.x) return ((a.x-b.x)*a.y-(a.y-b.y)*(a.x-c.x)<=c.y*(a.x-b.x));
    else
    if(a.x==b.x) return((a.x-c.x)*(b.x-c.x)<=0&&(a.y-c.y)*(b.y-c.y)<=0);
}

int verif(punct c)
{
    int i,cnt=0;
    for(i=1;i<=n-1;i++) if(coliniaritate(c,a[i],a[i+1])) return 1;
    if(coliniaritate(c,a[n],a[1])) return 1;
    for(i=1;i<=n-1;i++) if((c.x-a[i].x)*(c.x-a[i+1].x)<=0&&sol(c,a[i],a[i+1]))cnt++;
    if((c.x-a[n].x)*(c.x-a[1].x)<=0&&sol(c,a[n],a[1]))cnt++;
    if(cnt%2==1)return 1;
    return 0;
}

int main()
{
    FILE *f=fopen("poligon.in","r");
    FILE *g=fopen("poligon.out","w");
    fscanf(f,"%d %d",&n,&m);
    for(i=1;i<=n;i++)fscanf(f,"%d %d",&a[i].x,&a[i].y);
    for(i=1;i<=m;i++)
    {
        fscanf(f,"%d %d",&c.x,&c.y);
        if(verif(c)) cnt++;
    }
    fprintf(g,"%d",cnt);
    fclose(f);
    fclose(g);
}