Cod sursa(job #2014090)

Utilizator Bodo171Bogdan Pop Bodo171 Data 22 august 2017 21:21:01
Problema Poligon Scor 20
Compilator cpp Status done
Runda Arhiva de probleme Marime 3.88 kb
#include <iostream>
#include <fstream>
#include <vector>
#include <algorithm>
#include <cmath>
using namespace std;
const int nmax=805;
typedef long double ldouble;
struct dreapta
{
    ldouble a,b,I;
    int xst,xdr;
}lat[nmax];
vector<dreapta> d[nmax],fx[nmax];
vector< pair<int,int> > segm[nmax];
ldouble Py;
ldouble eps=0.000000001;
bool skp;
double inter(ldouble y,dreapta d)
{
     if(d.xst==d.xdr)
        return (d.xst);
    return ((y-d.b)/d.a);
}
bool comp(dreapta unu,dreapta doi)
{
    if(unu.I!=doi.I)
        return (unu.I<doi.I);
    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];
ldouble xdif,ydif,x,y,A,B;
void preccalc()
{
    for(i=1;i<=nr;i++)
    {
        Py=ynorm[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]});
               }
               skp=0;
               if(Y[j]==Y[j+1])
               {
                    segm[i].push_back({Xst,Xdr});
               }
               else
               {
                   lat[j].I=inter(Py,lat[j]);
                   //vezi de ce nu merge cand faci asa
                   if(Y[j]==ynorm[i]&&min(Y[j-1],Y[j+1])<Y[j]&&max(Y[j-1],Y[j+1])>Y[j]&&j>1) skp=1;
                   if(!skp) fx[i].push_back(lat[j]);
                   if(max(Y[j],Y[j+1])>ynorm[i])d[i].push_back(lat[j]);
                   //cout<<lat[j].I<<' '<<d[i].back().I<<'\n';
               }
           }
        }
        sort(d[i].begin(),d[i].end(),comp);
        sort(fx[i].begin(),fx[i].end(),comp);
        sort(segm[i].begin(),segm[i].end());
    }
}
bool intersect(dreapta d,ldouble x,ldouble y)
{
    return (inter(y,d)<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;
    }
    if(yq==ynorm[wh])
    {
         sz=fx[wh].size();ret=0;
        for(p=lg[sz];p>=0;p--)
       {
        if(ret+(1<<p)<=sz&&intersect(fx[wh][ret+(1<<p)-1],xq,yq))
           ret+=(1<<p);
       }
       x=xq;
       if(ret<sz&&inter(yq,fx[wh][ret])==x)
         return 1;
    }
    else
    {
         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);
          }
      x=xq;
      if(ret<sz&&inter(yq,d[wh][ret])==x)
         return 1;
    }
    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];
    Y[n+2]=-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();lg[0]=-1;
    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;
}