Cod sursa(job #1670621)

Utilizator badea_adi1999Badea Adrian Catalin badea_adi1999 Data 31 martie 2016 21:30:51
Problema Poligon Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.04 kb
#include <cstdio>
#include <algorithm>
#include <vector>
#define nmax 805
#define eps 0.000001
using namespace std;
int n,m,k,r,a[nmax],b[nmax],sol;
struct point{int x;int y;};
point p[nmax],aux,q;
struct segm{point a;point b;} s[nmax],segment;
vector <segm> v[nmax];

bool pointcomp(const point &a,const point &b)
{
    if (a.x!=b.x)
        return a.x<b.x;
    return a.y<b.y;
}
double inter(const segm &a,int r)
{
    return (a.a.y*(a.b.x-a.a.x)-a.a.x*(a.b.y-a.a.y))/(a.b.x-a.a.x);
}
bool segmcomp(const segm &p,const segm &q)
{
    return inter(p,r)+inter(p,r+1)<inter(q,r)+inter(q,r+1);
}

void checksegm(segm p,int i)
{
    if (p.a.x<=b[i]&&b[i]<=p.b.x&&p.a.x<=b[i+1]&&b[i+1]<=p.b.x)
        v[i].push_back(p);
}
long long determinant(const point &a,const point &b,const point &c)
{
    return (b.x-a.x)*(c.y-a.y)-(c.x-a.x)*(b.y-a.y);
}
int main()
{
    int i,j,t;
    freopen("poligon.in","r",stdin);
    freopen("poligon.out","w",stdout);
    scanf("%d %d",&n,&m);
    for (i=1;i<=n;i++)
        scanf("%d %d",&p[i].x,&p[i].y);
    p[n+1]=p[1];
    for (i=1;i<=n;i++)
        a[i]=p[i].x;
    sort(a+1,a+n+1);
    for (i=1;i<=n;i++) {
        if (i==1||a[i]!=a[i-1]) {
            b[++k]=a[i];
        }
    }
    for (i=1;i<=n;i++) {
        s[i].a=p[i];
        s[i].b=p[i+1];
        if (pointcomp(p[i+1],p[i]))
            swap(s[i].a,s[i].b);
    }
    for (i=1;i<k;i++)
        for (j=1;j<=n;j++)
            checksegm(s[j],i);

    for (i=1;i<k;i++) {
        r=i;
        sort(v[i].begin(),v[i].end(),segmcomp);
    }
    for (i=1;i<=m;i++) {
        scanf("%d %d",&q.x,&q.y);
        int t=1;
        for (j=1<<9;j;j>>=1)
            if (t+j<k&&q.x>=b[t+j])
                t+=j;
        r=-1;
        for (j=1<<9;j;j>>=1)
            if (r+j<v[t].size())
                if (determinant(v[t][r+j].a,v[t][r+j].b,q)>=0)
                    r+=j;
        if (determinant(v[t][r+j].a,v[t][r+j].b,q)==0)
            r=0;
        sol+=(++r)&1;
    }
    printf("%d\n",sol);
    return 0;
}