Cod sursa(job #1992107)

Utilizator andreistanStan Andrei andreistan Data 19 iunie 2017 14:31:15
Problema Poligon Scor 50
Compilator cpp Status done
Runda Arhiva de probleme Marime 3.7 kb
#include <iostream>
#include <fstream>
#include <algorithm>
using namespace std;
ifstream f("poligon.in");
ofstream g("poligon.out");
const int INF=1000001;
struct punct
{
    int x, y;
};

punct vf[802];
double banda[802];
int N, K;

void citirevf()
{
    f >> N >> K;
    for(int i = 1; i <= N; i++)
    {
        f >> vf[i].x >> vf[i].y;
        banda[i] = vf[i].x;
    }
    vf[N+1]=vf[1];
}

void pastdis(double v[], int &lg)
{
    int nr = 1;
    for(int i = 2; i <= lg; i++)
        if(v[i] > v[i - 1])
            v[++nr] = v[i];
    lg = nr;
}

int comp(double x, double y)
{
    return x < y;
}

long long det(const punct &A, const punct &B, const punct &C)
{
    // > 0 => spre stanga
    return (long long)(A.x - B.x) * (B.y - C.y) - (long long)(A.y - B.y) * (B.x - C.x);
}

int cautbin(double x, int &ind)
{
    int st = 1, dr = N, mij;
    if(x < banda[1] || x > banda[N])
        return 0;
    while(st <= dr)
    {
        mij = (st + dr) / 2;
        if(x > banda[mij])
        {
            if(x < banda[mij + 1])
            {
                ind = mij;
                return 1;
            }
            st = mij + 1;
        }
        else if(x < banda[mij])
            dr = mij - 1;
        else //x==banda[mij]
        {
            ind = mij;
            return 1;
        }
    }
}

int main()
{
    citirevf();
    sort(banda + 1, banda + N + 1, comp);
    int lgb = N, nrint=0;
    pastdis(banda, lgb);
    banda[lgb+1]=INF;
    // for(int i = 1; i <= lgb; i++)
    //    cout << banda[i] << ' ';
    //cout << endl;
    for(int q = 1; q <= K; q++)
    {
        int ind;
        punct p;
        f >> p.x >> p.y;
        //cout<<"x="<<p.x<<endl;
        int rez = cautbin(p.x, ind);
        int nrlp;
        bool pelat;
        switch(rez)
        {
        case 1:
            // cout << banda[ind] << ' ' << banda[ind + 1] << '\n';
            nrlp=0;
            pelat=0;
            for(int i=1; i<=N; i++)
            {
                int j=i+1;

                if(vf[i].x==vf[j].x)
                {
                    if(p.x==vf[i].x)
                    {
                        int imaxy,iminy;
                        if(vf[i].y>vf[j].y)
                        {
                            imaxy=i;
                            iminy=j;
                        }
                        else
                        {
                            imaxy=j;
                            iminy=i;
                        }
                        if(vf[iminy].y<=p.y && p.y<=vf[imaxy].y)
                            nrint++;
                    }
                }
                else
                {
                    int imaxx,iminx;
                    if(vf[i].x>vf[j].x)
                    {
                        imaxx=i;
                        iminx=j;
                    }
                    else
                    {
                        imaxx=j;
                        iminx=i;
                    }
                    if(vf[iminx].x<=banda[ind] && banda[ind+1]<=vf[imaxx].x)
                    {
                        double dd=det(vf[iminx],vf[imaxx],p);
                        if(dd==0)
                        {
                            pelat=1;
                            break;
                        }
                        else if(dd>0)
                            nrlp++;
                    }
                }
            }
            if(pelat)
                nrint++;
            else if(nrlp%2!=0)
                nrint++;
            //else
            //g<<"NU\n";
            break;
        }
    }
    g<<nrint;
    return 0;
}