Cod sursa(job #1685685)

Utilizator margikiMargeloiu Andrei margiki Data 11 aprilie 2016 20:05:07
Problema Poligon Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.28 kb
//18:45
# include <bits/stdc++.h>
# define NR 1005
# define INF 999999999
using namespace std;
ifstream f("poligon.in");
ofstream g("poligon.out");
vector <int> v[NR];
struct elem {
    int x, y;
}p[NR];
bool cmp (int x, int y) {
    double midx=((double)(p[x].x + p[x+1].x)/2),
           midy=((double)(p[y].x + p[y+1].x)/2);
    return midx < midy;
}

int i,j,n,m,x,y,online,sol,ci,cs,mij,poz,POZ,Q,nrX,VV;
int A[NR], B[NR], C[NR], X[NR];
double panta[NR];

bool sus (int x, int y, int D) {
    if (A[D]*x + B[D]*y + C[D]==0) online=1;

    elem E;
    if (p[D].x < p[D+1].x) E=p[D];
                      else E=p[D+1];
    double P1=((double)(y - E.y))/(x - E.x);

    if (P1 > panta[D]) return 1;
                  else return 0;
}
int main ()
{
    f>>n>>Q;
    for (int i=1; i<=n; ++i) {
        f>>p[i].x>>p[i].y;
        X[++nrX]=p[i].x;
    }
    p[n+1]=p[1];
    //detalii segmente
    for (i=1; i<=n; ++i) {
        A[i]=p[i].y - p[i+1].y;
        B[i]=p[i+1].x - p[i].x;
        C[i]=1LL*p[i].x * p[i+1].y - 1LL*p[i+1].x * p[i].y;
        if (B[i]==0) {
            if (A[i]<0) panta[i]=INF;
                   else panta[i]=-INF;
        }
        else panta[i]=(double)(-A[i])/B[i];
    }

    //drepte
    VV=1; sort (X+1, X+nrX+1);
    for (int i=2; i<=nrX; ++i)
        if (X[i]!=X[VV]) X[++VV]=X[i];

    for (int i=1; i<=VV; ++i) {//fiecare dreapta
        for (int j=1; j<=n; ++j) {
            if (min(p[j].x, p[j+1].x)<=X[i] && X[i]<=max(p[j].x, p[j+1].x)) {
                v[i].push_back(j);
            }
        }
        sort (v[i].begin(), v[i].end(), cmp);
    }
    for (int i=1; i<=Q; ++i) {
        f>>x>>y;
        //caut binar fasia
        if (x<X[1] || X[VV]<x) continue;
        ci=1; cs=VV; poz=0;
        while (ci<=cs) {
            mij=(ci+cs)/2;
            if (X[mij]<=x) ci=mij+1, poz=mij;
                      else cs=mij-1;
        }

        // caut binar cate segmente sunt mai jos decat el
        online=0; ci=0; cs=v[poz].size()-1; POZ=-1;
        while (ci<=cs) {
            mij=(ci+cs)/2;
            if (sus(x, y, v[poz][mij])) ci=mij+1, POZ=mij;
                                   else cs=mij-1;
        }
        if ((POZ+1)%2==1 || online) ++sol;
    }
    g<<sol<<"\n";

    return 0;
}