Cod sursa(job #2242016)

Utilizator Bodo171Bogdan Pop Bodo171 Data 17 septembrie 2018 16:27:47
Problema Poligon Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.55 kb
#include <iostream>
#include <fstream>
#include <cassert>
#include <map>
using namespace std;
struct point
{
    long double x,y;
}v[1005];
map< pair<int,int>,int > m;
long long det(point A,point B,point C)
{
    return 1LL*A.x*B.y+B.x*A.y+C.x*A.y-A.y*B.x-B.y*C.x-C.y*A.x;
}
long long sgn(long long a)
{
    if(a<0) return -1;
    if(a==0) return 0;
    return 1;
}
int n,q,x,y;
long double A,B;
int check(long double x,long double y)
{
    point pct;
    pct.x=x;pct.y=y;
    if(m[make_pair(x,y)])
        return 1;
    int cate=0;
    for(int i=1;i<=n;i++)
    {
        if(det(v[i],v[i+1],pct)==0&&min(v[i].x,v[i+1].x)<=x&&max(v[i].x,v[i+1].x)>=x&&min(v[i].y,v[i+1].y)<=y&&max(v[i].y,v[i+1].y)>=y)
            return 1;
        if(min(v[i].x,v[i+1].x)>x||(max(v[i].x,v[i+1].x)<x))
            continue;
        if(v[i].x==v[i+1].x)
        {
            /*if(x==v[i].x&&max(v[i].y,v[i+1].y)>=y)
                cate++;*/
        }
        else
        {
            A=((long double)(v[i+1].y-v[i].y))/((long double)(v[i+1].x-v[i].x));
            B=(long double)(v[i].y-A*v[i].x);
            cate+=((long double)A*x+B>=(long double) y);
        }
    }
    return (cate%2);
}
int main()
{
    ifstream f("poligon.in");
    ofstream g("poligon.out");
    f>>n>>q;
    for(int i=1;i<=n;i++)
    {
        f>>v[i].x>>v[i].y;
        m[make_pair(v[i].x,v[i].y)]=1;
    }
    v[n+1]=v[1];
    int ans=0;
    for(int cnt=1;cnt<=q;cnt++)
    {
        f>>x>>y;
        ans+=check(x,y);
    }
    g<<ans;
    return 0;
}