Cod sursa(job #2147539)

Utilizator nurof3nCioc Alex-Andrei nurof3n Data 28 februarie 2018 20:10:46
Problema Poligon Scor 70
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.67 kb
#include <iostream>
#include <fstream>
#include <algorithm>
using namespace std;
ifstream f ("poligon.in");
ofstream g ("poligon.out");
struct punct
{
    double x, y;
} p[801];
struct latura
{
    punct A, B;
} l[801], L[801][801];
int N, K, nrf, nL[801];
bool cmp (punct A, punct B)
{
    if (A.x == B.x) return A.y < B.y;
    return A.x < B.x;
}
bool cmpl (latura l1, latura l2)
{
    return (l1.A.y + l1.B.y) < (l2.A.y + l2.B.y);
}
double det_arie (punct A, punct B, punct C)
{
    return (A.x - B.x) * (B.y - C.y) - (B.x - C.x) * (A.y - B.y);
}
punct intersectie_dr (latura l, double x)
{
    punct pct;
    pct.x = x;
    if (l.A.y == l.B.y) pct.y = l.A.y;
    else pct.y = l.A.y - (l.A.x - x) * (l.B.y - l.A.y) / (l.B.x - l.A.x);
    return pct;
}
int cautfasie (punct pct)
{
    int st = 1, dr = nrf, m;
    while (st <= dr)
    {
        m = st + (dr - st) / 2;
        if (pct.x >= p[m].x && pct.x <= p[m + 1].x) return m;
        else if (pct.x < p[m].x) dr = m - 1;
        else st = m + 1;
    }
    return m;
}
int nrlatsub (int fasie, punct pct)
{
    int nr = 0;
    for (int i = 1; i <= nL[fasie]; i++)
    {
        double det = det_arie (pct, L[fasie][i].A, L[fasie][i].B);
        if (det == 0) return 1;
        if (det > 0) nr++;
    }
    return nr;
}
bool interior (punct pct)
{
    if (pct.x < p[1].x || pct.x > p[nrf].x) return 0;
    int fasie = cautfasie (pct);
    int latsub = nrlatsub (fasie, pct);
    if (latsub % 2 == 1) return 1;
    return 0;
}
int main()
{
    f >> N >> K;

    f >> p[1].x >> p[1].y;
    for (int i = 2; i <= N; i++)
    {
        f >> p[i].x >> p[i].y;
        l[i - 1].A = p[i - 1], l[i - 1].B = p[i];
        if (cmp (l[i - 1].B, l[i - 1].A) ) swap (l[i - 1].A, l[i - 1].B);
    }
    l[N].A = p[N], l[N].B = p[1];
    if (cmp (l[N].B, l[N].A) ) swap (l[N].A, l[N].B);
    //determinarea fasiilor
    sort (p + 1, p + N + 1, cmp);
    nrf = 1;
    for (int i = 2; i <= N; i++)
        if (p[i].x != p[i - 1].x) p[++nrf] = p[i];
    //determinarea si sortarea dupa y a laturilor din fiecare fasie
    for (int i = 1; i < nrf; i++)
    {
        nL[i] = 0;
        for (int j = 1; j <= N; j++)
            if (l[j].A.x <= p[i].x && l[j].B.x >= p[i + 1].x)
            {
                nL[i]++;
                L[i][nL[i]].A = intersectie_dr (l[j], p[i].x);
                L[i][nL[i]].B = intersectie_dr (l[j], p[i + 1].x);
            }
        sort (L[i] + 1, L[i] + nL[i] + 1, cmpl);
    }
    punct pct;
    int sol = 0;
    for (int i = 1; i <= K; i++)
    {
        f >> pct.x >> pct.y;
        if (interior (pct) ) sol++;
    }
    g << sol << '\n';
    return 0;
}