Cod sursa(job #1992756)

Utilizator andreistanStan Andrei andreistan Data 21 iunie 2017 12:46:55
Problema Poligon Scor 50
Compilator cpp Status done
Runda Arhiva de probleme Marime 3.91 kb
#include <iostream>
#include <fstream>
#include <algorithm>
using namespace std;
ifstream f("poligon.in");
ofstream g("poligon.out");
const int INF = 1000001;
struct punct
{
    double x, y;
};
struct dreapta
{
    double a, b, c;
};
struct segm
{
    punct A, B;
};
struct lat_banda
{
    int nrlat;
    segm v[802];
};
punct vf[802];
lat_banda b[802];
double banda[802];
int N, K, lgb;

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

inline dreapta ecuatie(punct A, punct B)
{
    dreapta d;
    d.a = A.y - B.y;
    d.b = B.x - A.x;
    d.c = A.x * B.y - B.x * A.y;
    return d;
}

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

int comp2(segm AB, segm CD)
{
    return AB.A.y + AB.B.y < CD.A.y + CD.B.y;
}

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

int cautbin_pct(punct P, lat_banda b)
{
    int st = 1, dr = b.nrlat, mij, nr = 0;
    while(st <= dr)
    {
        mij = (st + dr) / 2;
        double dd = det(b.v[mij].A, b.v[mij].B, P);
        if(dd > 0)
        {
            st = mij + 1;
            nr = mij;
        }
        else
            if(dd < 0)
                dr = mij - 1;
            else //dd == 0
                return 1;
    }
    return nr % 2;
}

int cautbin(double x, int &ind)
{
    int st = 1, dr = lgb - 1, mij;
    if(x < banda[1] || x > banda[lgb])
        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 nrint = 0;
    lgb = N;
    pastdis(banda, lgb);
    banda[lgb + 1] = INF;
    // for(int i = 1; i <= lgb; i++)
    //    cout << banda[i] << ' ';
    //cout << endl;
    for(int q = 1; q <= lgb; q++)
    {
        for(int i = 1; i <= N; i++)
        {
            int j = i + 1;
            int imaxx, iminx;
            if(vf[i].x > vf[j].x)
            {
                imaxx = i;
                iminx = j;
            }
            else
            {
                imaxx = j;
                iminx = i;
            }
            if(vf[iminx].x <= banda[q] && banda[q + 1] <= vf[imaxx].x)
            {
                dreapta d;
                d = ecuatie(vf[i], vf[j]);
                if(d.b != 0)
                {
                    segm AB;
                    AB.A.x = banda[q];
                    AB.B.x = banda[q + 1];
                    AB.A.y = (-d.a * banda[q] - d.c) / d.b;
                    AB.B.y = (-d.a * banda[q + 1] - d.c) / d.b;
                    b[q].v[++b[q].nrlat] = AB;
                }
            }
        }
        sort(b[q].v + 1, b[q].v + 1 + b[q].nrlat, comp2);
    }
    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);
        b[0].nrlat = 0;
        switch(rez)
        {
        case 1:
            if(cautbin_pct(p, b[ind]))
                nrint++;
            break;
        case -1:
            if(cautbin_pct(p, b[ind]) || cautbin_pct(p, b[ind - 1]))
                nrint++;
        }
    }
    g << nrint;
    return 0;
}