Cod sursa(job #3241620)

Utilizator Anul2024Anul2024 Anul2024 Data 1 septembrie 2024 15:07:11
Problema Poligon Scor 0
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 3.49 kb
#include <fstream>
#include <algorithm>
#include <map>
#include <vector>
#define ld long double
#define mk make_pair
#define x first
#define y second
#define y1 yy1
using namespace std;
ifstream fin ("poligon.in");
ofstream fout ("poligon.out");
int k,n,q,pozx1,pozx2,i,j,poz,pozi,nrc,y1,y2,val,fr[60001],l[801];
pair <int,int> p[801],pct1,pct2,pct;
vector <pair <int,int>> d[60001];
vector <pair <ld,ld>> v[801];
map <pair <int,int>,bool> frp;
ld coordy (pair <ld,ld> a,pair <ld,ld> b,ld x)
{
    ///(b.y-a.y)/(b.x-a.x)=(val-a.y)/(x-a.x)
    ///(val-a.y)=(b.y-a.y)*(x-a.x)/(b.x-a.x)
    ld val=(b.y-a.y)*(x-a.x)/(b.x-a.x);
    val+=a.y;
    return val;
}
int f (pair <ld,ld> a,pair <ld,ld> b,pair <ld,ld> c)
{
    int e=(b.y-a.y);
    int f=(b.x-a.x);
    int g=(c.x-a.x);
    int h=(c.y-a.y);
    if (f<0)
    {
        f=-f;
        e=-e;
    }
    if (f==0)
        e=1e8;
    if (h<0)
    {
        h=-h;
        g=-g;
    }
    if (h==0)
        g=1e8;
    int val=e*h-g*f;
    return val;
}
int cbpoz (int x)
{
    int st=1,dr=k,mij;
    while (st<=dr)
    {
        mij=(st+dr)/2;
        if (l[mij]>x)
            dr=mij-1;
        else
            st=mij+1;
    }
    return dr;
}
int cb (pair <int,int> pct,int poz)
{
    int st=0,dr=v[poz].size ()-1,mij;
    while (st<=dr)
    {
        mij=(st+dr)/2;
        if (f (mk (l[poz],v[poz][mij].x),mk (l[poz+1],v[poz][mij].y),pct)<=0)
            st=mij+1;
        else
            dr=mij-1;
    }
    return dr+1;
}
int cb2 (vector <pair <int,int>> &v,int x)
{
    int st=0,dr=v.size (),mij;
    while (st<=dr)
    {
        mij=(st+dr)/2;
        if (v[mij].x<=x)
            st=mij+1;
        else
            dr=mij-1;
    }
    return dr;
}
int main ()
{
    fin>>n>>q;
    for (i=1; i<=n; i++)
    {
        fin>>p[i].x>>p[i].y;
        frp[make_pair (p[i].x,p[i].y)]=1;
        l[i]=p[i].x;
    }
    sort (l+1,l+n+1);
    k=1;
    for (i=2; i<=n; i++)
    {
        if (l[i]!=l[i-1])
            l[++k]=l[i];
    }
    for (i=1; i<=k; i++)
        fr[l[i]]=i;
    for (i=1; i<=n; i++)
    {
        j=i+1;
        if (j>n)
            j=1;
        pct1=p[i];
        pct2=p[j];
        if (pct1.x==pct2.x)
        {
            y1=pct1.y;
            y2=pct2.y;
            if (y1>y2)
                swap (y1,y2);
            d[pct1.x].push_back (mk (y1,y2));
        }
        if (pct1.x>pct2.x)
            swap (pct1,pct2);
        for (poz=fr[pct1.x]; poz<fr[pct2.x]; poz++)
        {
            pozx1=l[poz];
            pozx2=l[poz+1];
            v[poz].push_back (make_pair (coordy (pct1,pct2,pozx1),coordy (pct1,pct2,pozx2)));
        }
    }
    for (i=1; i<=k; i++)
        sort (v[i].begin (),v[i].end ());
    while (q--)
    {
        fin>>pct.x>>pct.y;
        if (frp.find (make_pair (pct.x,pct.y))!=frp.end ())
        {
            nrc++;
            continue;
        }
        if (!d[pct.x].empty ()&&d[pct.x][0].x<=pct.y)
        {
            val=cb2 (d[pct.x],pct.y);
            if (d[pct.x][val].y>=pct.y)
            {
                nrc++;
                continue;
            }
        }
        if (pct.x>=l[k]||pct.x<l[1])
            continue;
        poz=cbpoz (pct.x);
        pozi=cb (pct,poz);
        if (pozi!=0&&f (mk (l[poz],v[poz][pozi-1].x),mk (l[poz+1],v[poz][pozi-1].y),pct)==0)
        {
            nrc++;
            continue;
        }
        nrc+=(pozi%2!=0);
    }
    fout<<nrc;
    return 0;
}