Cod sursa(job #1201912)

Utilizator misinozzz zzz misino Data 26 iunie 2014 13:41:15
Problema Poligon Scor 70
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.5 kb
#include<fstream>
#include<algorithm>
#include<vector>

#define eps 0.000001
#define N 900
#define D 100000

using namespace std;

ifstream f("poligon.in");
ofstream g("poligon.out");

int i,j,n,m,nn,poz,ppoz = D,mij,b,nrb,pe,sol,li,ls,raspuns;

double x,y,band[N];

vector<int>a[N];

struct ecuatie{int a,b,c;}ec[N];
struct punct{int x,y;}v[N];

inline bool cmp(int x,int y){
    double mij = band[i] + band[i + 1];

    double y1 = (-ec[x].a * mij - 2.0 * ec[x].c) / ec[x].b;
    double y2 = (-ec[y].a * mij - 2.0 * ec[y].c) / ec[y].b;

    return y2 - y1 > eps;
}

inline bool verif(int k){
    if(x * ec[k].a + y * ec[k].b + ec[k].c == 0)
        pe = 1;

    double yy = (- x * ec[k].a - ec[k].c) / ec[k].b;

    return y >= yy;
}

char buf[D+2];

inline int ianr(){
    unsigned int nr=0;

    while((buf[ppoz] < '0' || buf[ppoz] > '9') && buf[ppoz] != '-')
        if(++ ppoz >= D)
        fread(buf , D , 1 , stdin) , ppoz = 0;

    while('0' <= buf[ppoz] && buf[ppoz] <= '9')
    {
        nr = nr * 10 + buf[ppoz] - '0';

        if(++ ppoz >= D)
            fread(buf , D , 1 , stdin) , ppoz = 0;
    }
    return nr;
}


int main()
{
    f >> n >> m;

    for(i = 1 ; i <= n ; ++ i)
    {
        f >> v[i].x >> v[i].y;

        band[++ nrb] = v[i].x;
    }
    v[n + 1] = v[1];

    for(i = 1 ; i <= n ; ++ i)
    {
        ec[i].a = v[i].y - v[i + 1].y;
        ec[i].b = v[i + 1].x - v[i].x;
        ec[i].c = v[i].x * v[i + 1].y - v[i + 1].x * v[i].y;
    }

    sort(band + 1 , band + nrb + 1);

    nn =  1;

    for(i = 2 ; i <= nrb ; ++ i)
        if(band[i - 1] != band[i])
            band[++ nn] = band[i];

    nrb = nn;

    for(i = 1 ; i <= nrb ; ++ i)
    {
        for(j = 1 ; j <= n ; ++ j)
        if(min(v[j].x , v[j + 1].x) <= band[i] && max(v[j].x , v[j + 1].x) > band[i])
            a[i].push_back(j);

        sort(a[i].begin(),a[i].end(),cmp);
    }

    for(; m ; -- m)
    {
        f >> x >> y;

        if(x < band[1] || x > band[nrb])
            continue;

        b = 0;

        for(i = 10 ; i >= 0 ; -- i)
            if(b + (1 << i) <= nrb && band[b + (1 << i )] < x)
            b += (1 << i);

        pe = 0;
        poz = 0;

        for(i = 10 ; i >= 0; -- i)
            if(poz + (1 << i) <= a[b].size() && verif(a[b][poz + (1 << i) - 1]))
                poz += (1 << i);

        if(pe || (poz & 1))
            ++ raspuns;
    }

    g << raspuns << '\n';

    return 0;
}