Cod sursa(job #1992441)

Utilizator zdavid112zIon David-Gabriel zdavid112z Data 20 iunie 2017 14:35:53
Problema Poligon Scor 10
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.79 kb
#include <bits/stdc++.h>
#define eps 1e-6

using namespace std;

struct Punct
{
    int x, y;
} v[810];

struct Dreapta
{
    int a, b, c;

    void init(const Punct& p1, const Punct& p2)
    {
        a = p1.y - p2.y;
        b = p2.x - p1.x;
        c = p1.x * p2.y - p2.x * p1.y;
    }
};

int vx[810];
vector<Dreapta> vf[810];
int st, dr, n, lvx;

int calc_y(Dreapta d, int x)
{
    return (-d.a * x - d.c) / d.b;
}

bool cmp(Dreapta da, Dreapta db)
{
    int ya = calc_y(da, (st + dr) / 2);
    int yb = calc_y(db, (st + dr) / 2);
    return ya < yb;
}

int cautb_vx(int x)
{
    int st = 0, dr = lvx - 1, mij;
    while(st <= dr)
    {
        mij = (st + dr) / 2;
        if(vx[mij] == x)
            return mij;
        else
            if(vx[mij] < x)
                st = mij + 1;
            else dr = mij - 1;
    }
    return mij;
}

int cautb_vx2(int x)
{
    int st = 0, dr = lvx - 1, mij;
    while(st <= dr)
    {
        mij = (st + dr) / 2;
        if(vx[mij] <= x && x <= vx[mij + 1])
            return mij;
        else
            if(vx[mij] < x)
                st = mij + 1;
            else
                dr = mij - 1;
    }
    return mij;
}

int cautb_fs(const vector<Dreapta>& v, Punct p)
{
    int st = 0, dr = v.size() - 1, mij, rez = -1;
    while(st <= dr)
    {
        mij = (st + dr) / 2;
        int y = calc_y(v[mij], p.x);
        if(y == p.y)
            return 1;
        else
            if(y < p.y)
            {
                st = mij + 1;
                rez = mij;
            }
            else
                dr = mij - 1;
    }
    return (rez + 1) % 2;
}

int main()
{
    freopen("poligon.in", "r", stdin);
    freopen("poligon.out", "w", stdout);
    int k;
    scanf("%d%d", &n, &k);
    for(int i = 0; i < n; i++)
    {
        scanf("%d%d", &v[i].x, &v[i].y);
        vx[i] = v[i].x;
    }
    v[n] = v[0];
    sort(vx, vx + n);
    lvx = 1;
    for(int i = 1; i < n; i++)
    {
        if(vx[i] != vx[i - 1])
            vx[lvx++] = vx[i];
    }
    for(int i = 0; i < n; i++)
    {
        Dreapta dreapta;
        dreapta.init(v[i], v[i + 1]);
        int fs = cautb_vx(v[i].x);
        int fd = cautb_vx(v[i + 1].x);
        if(fs > fd) swap(fs, fd);
        for(; fs < fd; fs++)
            vf[fs].push_back(dreapta);
    }
    for(int i = 0; i < lvx - 1; i++)
    {
        st = vx[i];
        dr = vx[i + 1];
        sort(vf[i].begin(), vf[i].end(), cmp);
    }
    int rez = 0;
    for(int i = 0; i < k; i++)
    {
        Punct p;
        scanf("%d%d", &p.x, &p.y);
        if(p.x < vx[0] || p.x > vx[lvx - 1])
            continue;
        int fas = cautb_vx2(p.x);
        rez += cautb_fs(vf[fas], p);
    }
    printf("%d", rez);
    return 0;
}