Cod sursa(job #1991097)

Utilizator nurof3nCioc Alex-Andrei nurof3n Data 15 iunie 2017 09:51:50
Problema Poligon Scor 70
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.77 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 st = 1, dr = nL[fasie], m;
    if(det_arie(pct, L[fasie][st].A, L[fasie][st].B) < 0) return 0;
    if(det_arie(pct, L[fasie][dr].A, L[fasie][dr].B) > 0) return 0;
    while(st < dr)
    {
        m = st + (dr - st + 1) / 2;
        if(det_arie(pct, L[fasie][m].A, L[fasie][m].B) > 0) st = m;
        else dr = m - 1;
    }
    return st;
}
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;
}