Cod sursa(job #2013813)

Utilizator Bodo171Bogdan Pop Bodo171 Data 22 august 2017 14:40:47
Problema Poligon Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.78 kb
#include <iostream>
#include <fstream>
#include <vector>
#include <algorithm>
using namespace std;
const int nmax=805;
struct dreapta
{
    double a,b;
    int xst,xdr;
}lat[nmax];
vector<dreapta> d[nmax];
vector< pair<int,int> > segm[nmax];
bool comp(dreapta unu,dreapta doi)
{
    if(unu.xst==doi.xst) return unu.xdr<doi.xdr;
    return unu.xst<doi.xst;
}
int n,m,tot,ret,wh,p,i,j,nr,xq,yq,Xst,Xdr,sz;
int X[nmax],Y[nmax],ynorm[nmax],lg[nmax];
double xdif,ydif,x,y,A,B;
void preccalc()
{
    for(i=1;i<=nr;i++)
    {
        for(j=1;j<=n;j++)
        {
           if(min(Y[j],Y[j+1])<=ynorm[i]&&max(Y[j],Y[j+1])>=ynorm[i])
           {
               Xst=min(X[j],X[j+1]);Xdr=max(X[j],X[j+1]);
               if(Y[j]==ynorm[i]&&Y[j+1]!=ynorm[i])
               {
                   segm[i].push_back({X[j],X[j]});
               }
               if(Y[j]==Y[j+1])
               {
                   segm[i].push_back({Xst,Xdr});
               }
               else
               {
                   d[i].push_back(lat[j]);
               }
           }
        }
        sort(d[i].begin(),d[i].end(),comp);
        sort(segm[i].begin(),segm[i].end());
    }
}
bool intersect(dreapta d,double x,double y)
{
    if(d.xst==d.xdr)
        return (d.xst<x);
    return ((y-d.b)/d.a<x);
}
int query()
{
    wh=0;
    if(yq>ynorm[nr])
        return 0;
    for(p=lg[nr];p>=0;p--)
        if(wh+(1<<p)<=nr&&ynorm[wh+(1<<p)]<=yq)
           wh+=(1<<p);
    if(yq==ynorm[wh])
    {
        sz=segm[wh].size();ret=0;
        for(p=lg[sz];p>=0;p--)
        {
            if(ret+(1<<p)<=sz&&segm[wh][ret+(1<<p)-1].first<=xq)
                ret+=(1<<p);
        }
        ret--;
        if(ret>=0&&segm[wh][ret].second>=xq)
                return 1;
    }
    sz=d[wh].size();ret=0;
    for(p=lg[sz];p>=0;p--)
    {
        if(ret+(1<<p)<=sz&&intersect(d[wh][ret+(1<<p)-1],xq,yq))
            ret+=(1<<p);
    }
    return (sz-ret)%2;
}
int main()
{
    ifstream f("poligon.in");
    ofstream g("poligon.out");
    f>>n>>m;
    for(i=1;i<=n;i++)
    {
        f>>X[i]>>Y[i];
        ynorm[i]=Y[i];
    }
    X[n+1]=X[1];Y[n+1]=Y[1];
    for(i=1;i<=n;i++)
    {
        xdif=X[i+1]-X[i];
        ydif=Y[i+1]-Y[i];
        x=X[i];y=Y[i];
        A=ydif/xdif;
        B=y-A*x;
        lat[i].a=A;lat[i].b=B;
        lat[i].xst=min(X[i],X[i+1]);
        lat[i].xdr=max(X[i],X[i+1]);
    }
    sort(ynorm+1,ynorm+n+1);
    ynorm[0]=-1;
    for(i=1;i<=n;i++)
    {
        if(ynorm[i]!=ynorm[nr])
        {
            ++nr;
            ynorm[nr]=ynorm[i];
        }
    }
    preccalc();
    for(i=2;i<=n;i++)
        lg[i]=lg[i/2]+1;
    for(i=1;i<=m;i++)
    {
        f>>xq>>yq;
        tot+=query();
    }
    g<<tot;
    return 0;
}