Cod sursa(job #813128)

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

int i,j,n,m,xo,yo,nr=0;
struct coord
{
    int x,y;
};
coord a[801];
bool interior(int xo,int yo)
{
    int i,intersectii=0;
    int 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;
            }
            else
            {
            if(a[i].y>yo)
            continue;

            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;
}