Cod sursa(job #813122)

Utilizator lily3Moldovan Liliana lily3 Data 14 noiembrie 2012 22:22:49
Problema Poligon Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.19 kb
#include<fstream>
#include<cmath>
using namespace std;
ofstream g("poligon.out");

int i,j,n,m,xo,yo,nr=0;
struct coord
{
    double x,y;
};
coord a[801];
bool interior(double xo,double yo)
{
    int i,intersectii=0;
    double yy;
    for(i=1;i<=n;++i)
    {
        if((a[i].x<xo&&xo<a[i+1].x)||(a[i].x>xo&&xo>a[i+1].x))
        {
            yy=((xo*(a[i].y-a[i+1].y)+a[i].x*a[i+1].y-a[i+1].x*a[i].y));
            yy=yy/(a[i].x-a[i+1].x);
            if(yo==yy)
            return 1;

            if(yo>yy)
            ++intersectii;
        }
        if(xo==a[i].x)
        {
            if(a[i].y==yo)
            return 1;

            if(a[i+1].x==xo)
            if((a[i].y>yo&&yo>a[i+1].y)||(a[i].y<yo&&yo<a[i+1].y))
            return 1;

            if((a[i+1].x<xo&&a[i-1].x>xo)||(a[i+1].x>xo&&a[i-1].x<xo))
            ++intersectii;
        }
    }
    return intersectii%2;
}
int main()
{
    ifstream f("poligon.in");

    f>>n>>m;
    for(i=1;i<=n;++i)
    f>>a[i].x>>a[i].y;
    a[0]=a[n];
    a[n+1]=a[1];
    for(i=1;i<=m;++i)
    {
        f>>xo>>yo;
        if(interior(xo,yo))
        ++nr;
    }
    g<<nr<<"\n";
    return 0;
}