Cod sursa(job #1951785)

Utilizator badea_adi1999Badea Adrian Catalin badea_adi1999 Data 3 aprilie 2017 19:53:53
Problema Poligon Scor 80
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.61 kb
#include <cstdio>
#include <algorithm>
#include <vector>
#define nmax 805
#define eps 1e-10
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;
struct pointd{long double x;long double y;} q1;
struct segmd{pointd a;pointd b;};
vector <segmd> 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;
}
void ecuatiadreptei(const point &a,const point &b,long double &a1,long double &b1,long double &c1)
{
    if (abs(a.x-b.x)<=eps) {
        a1=1;b1=0;c1=-a.x;
        return;
    }
    if (abs(a.y-b.y)<=eps) {
        a1=0;b1=1;c1=-a.y;
        return;
    }
    a1=b.y-a.y;
    b1=a.x-b.x;
    c1=a.y*(b.x-a.x)-a.x*(b.y-a.y);
}

long double inter(const segm &a,int r)
{
    long double a1,b1,c1;
    ecuatiadreptei(a.a,a.b,a1,b1,c1);
    return (-c1-a1*b[r])/b1;
}
bool segmcomp(const segmd &p,const segmd &q)
{
    return p.a.y+p.b.y<q.a.y+q.b.y;;
}

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) {
        segmd k;
        k.a.x=b[i];
        k.a.y=inter(p,i);
        k.b.x=b[i+1];
        k.b.y=inter(p,i+1);
        v[i].push_back(k);
    }
}
long double determinant(pointd &a,pointd &b,pointd &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);
        q1.x=q.x;q1.y=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,q1)>=0)
                    r+=j;
        if (determinant(v[t][r+j].a,v[t][r+j].b,q1)==0)
            r=0;
        sol+=(++r)&1;
    }
    printf("%d\n",sol);
    return 0;
}