Cod sursa(job #2633244)

Utilizator AokijiAlex M Aokiji Data 6 iulie 2020 20:11:20
Problema Poligon Scor 20
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.29 kb

#include <iostream>
#include <fstream>
#define maxi 60009

using namespace std;

int n,m,x[805],y[805],nr,xmin=maxi,ymin=maxi;

int verif(int xc,int yc)
{
    int xa,ya,xb,yb,nrint=0;
    long long det1,det2,det3,det4;
    for(int i=0;i<n-1;i++)
    {
        xa=x[i];
        ya=y[i];
        xb=x[i+1];
        yb=y[i+1];
        det1=(xa-xc)*(yb-yc)-(xb-xc)*(ya-yc);
        det2=(xa-xmin)*(yb-ymin)-(xb-xmin)*(ya-ymin);
        //if(det1==0&&((xc>xa&&xc<xb)||(xc<xa&&xc>xb))&&((yc>ya&&yc<yb)||(yc<ya&&yc>yb)))
            //return 1;
        if(det1*det2<=0)
        {
            det3=(xc-xa)*(ymin-ya)-(xmin-xa)*(yc-ya);
            det4=(xc-xb)*(ymin-yb)-(xmin-xb)*(yc-yb);
            if(det3*det4<=0)
            {
                nrint++;
            }
        }
    }
    if(nrint%2)
        return 1;
    return 0;
}

void fct()
{
    ifstream fin("poligon.in");
    fin>>n>>m;
    for(int i=0;i<n;i++)
    {
        fin>>x[i]>>y[i];
        if(x[i]<xmin)
            xmin=x[i];
        if(y[i]<ymin)
            ymin=y[i];
    }
    xmin--;
    ymin--;
    int a,b;
    for(int i=0;i<m;i++)
    {
        fin>>a>>b;
        nr+=verif(a,b);
    }
    ofstream fout("poligon.out");
    fout<<nr<<"\n";
}

int main()
{
    fct();
    return 0;
}