Cod sursa(job #1547589)

Utilizator tudormaximTudor Maxim tudormaxim Data 9 decembrie 2015 17:38:24
Problema Poligon Scor 100
Compilator cpp Status done
Runda Lista lui wefgef Marime 3.36 kb
#include <iostream>
#include <fstream>
#include <algorithm>
using namespace std;
const int nmax = 805;
const double eps = 1e-12;
struct punct {int x, y;} p[nmax];
struct dreapta
{
    double a, b, c;
    int x, xa, xb;
} d[nmax];

struct segment{ double xa, ya, xb, yb;} s[nmax][nmax];
int v[nmax], cnt[nmax];

inline bool cmp_punct(punct a, punct b)
{
    if(a.x != b.x) return a.x < b.x;
    return a.y < b.y;
}

inline int calc_ret(double a, double b)
{
    if(a+eps < b) return -1;
    if(b+eps < a) return 1;
    return 0;
}

inline bool cmp_segm(segment a, segment b)
{
    return a.ya + a.yb < b.ya + b.yb;
}

int bsearch_fasie(int x, int st, int dr)
{
    if(st < dr)
    {
        int mij=(st+dr)>>1;
        if(v[mij] == x) return mij;
        if(v[mij] < x) return bsearch_fasie(x, mij+1, dr);
        else return bsearch_fasie(x, st, mij-1);
    }
    if(v[st] > x) return st-1;
    return st;
}

inline int bsearch_segm(int x, int y, int lev, int st, int dr)
{
    if(st < dr)
    {
        double a, b, c, ym;
        int mij=(st+dr)>>1, ret;
        a=s[lev][mij].ya - s[lev][mij].yb;
        b=s[lev][mij].xb - s[lev][mij].xa;
        c=s[lev][mij].xa*s[lev][mij].yb - s[lev][mij].xb*s[lev][mij].ya;
        ym=-(a*x+c)/b;
        ret=calc_ret(ym, y);
        if(ret==-1) return bsearch_segm(x, y, lev, mij+1, dr);
        else if(ret==1) return bsearch_segm(x, y, lev, st, mij-1);
        else return -1;
    }
    double a, b, c, ym;
    a=s[lev][st].ya - s[lev][st].yb;
    b=s[lev][st].xb - s[lev][st].xa;
    c=s[lev][st].xa*s[lev][st].yb - s[lev][st].xb*s[lev][st].ya;
    ym=-(a*x+c)/b;
    int ret=calc_ret(ym, y);
    if(ret==0) return -1;
    if(ret==-1) return st;
    return st-1;
}

int main()
{

    ifstream fin ("poligon.in");
    ofstream fout ("poligon.out");
    ios_base::sync_with_stdio(false);
    int n, m, x, y, i, j, sol=0, pos;
    fin >> n >> m;
    for(i=1; i<=n; i++)
        fin >> p[i].x >> p[i].y;
    p[0]=p[n];
    for(i=0; i<n; i++)
    {
        d[i].a=p[i].y - p[i+1].y;
        d[i].b=p[i+1].x - p[i].x;
        d[i].c=p[i].x*p[i+1].y - p[i+1].x*p[i].y;
        d[i].x=p[i].x;
        if(d[i].b)
        {
            d[i].xa=p[i].x;
            d[i].xb=p[i+1].x;
            if(d[i].xa > d[i].xb) swap(d[i].xa, d[i].xb);
        }
        else
        {
            d[i].xa=p[i].y;
            d[i].xb=p[i+1].y;
            if(d[i].xa > d[i].xb) swap(d[i].xa, d[i].xb);
        }
    }

    sort(p+1, p+n+1, cmp_punct);
    v[0]=0;
    v[++v[0]]=p[1].x;
    for(i=2; i<=n; i++)
        if(p[i].x != v[v[0]]) v[++v[0]]=p[i].x;

    for(i=1; i<v[0]; i++)
    {
        cnt[i]=0;
        for(j=0; j<n; j++)
            if(calc_ret(d[j].b, 0) && d[j].xa <= v[i] && v[i+1] <= d[j].xb)
            {
                s[i][++cnt[i]].xa=v[i];
                s[i][cnt[i]].ya=-(d[j].a*v[i] + d[j].c)/d[j].b;
                s[i][cnt[i]].xb=v[i+1];
                s[i][cnt[i]].yb=-(d[j].a*v[i+1] + d[j].c)/d[j].b;
            }
        sort(s[i]+1, s[i]+cnt[i]+1, cmp_segm);
    }
    while(m--)
    {
        fin >> x >> y;
        if(x < v[1] || v[v[0]] < x) continue;
        pos=bsearch_fasie(x, 1, v[0]-1);
        pos=bsearch_segm(x, y, pos, 1, cnt[pos]);
        if(pos&1) sol++;
    }
    fout << sol;
    fin.close();
    fout.close();
    return 0;
}