Cod sursa(job #517080)

Utilizator S7012MYPetru Trimbitas S7012MY Data 27 decembrie 2010 18:49:16
Problema Poligon Scor 100
Compilator cpp Status done
Runda Lista lui wefgef Marime 2.53 kb
#include <iostream>
#include <fstream>
#include <algorithm>
#define x first
#define y second
#define DN 805
#define DM 60005
using namespace std;

typedef pair<int, int> PER;
int n,m,px[DN],dx[DN],dy[DN],ec[DN],nr[DN],sol;
PER p[DN];
pair<double, int> li[DN][DN];

void precalc() {//dreptele verticale
    double a,xnou,ynou;
    for(int i=1; i<n; ++i) if(px[i]!=px[i+1]) for(int j=1; j<=n; ++j)
        if (((p[j].x<=px[i])&&(p[j+1].x>=px[i+1])) || ((p[j+1].x<=px[i])&&(p[j].x>=px[i+1]))) {//apatine zonei
            if (p[j+1].y==p[j].y) ynou=p[j].y;
            else {
                a=(double)(p[j+1].x-p[j].x)/(p[j+1].y-p[j].y);
                xnou=(double)(px[i+1]+px[i])/2-p[j].x;
                ynou=(double)p[j].y+xnou/a;
            }
            li[i][++nr[i]].y=j;
            li[i][nr[i]].x=ynou;
        }
    for(int i=1; i<n; ++i) if(px[i]!=px[i+1]) sort(li[i]+1,li[i]+nr[i]+1);
}

void bs(PER pct) {
    if (pct.x<px[1]) return;
    int unde=lower_bound(px+1,px+n+1,pct.x)-px-1;

    for(;(px[unde+1]<pct.x)&&(unde<=n);++unde);
    for( ;(px[unde]==px[unde+1]) && (unde<=n); ++unde);
    if ((0==unde)||(unde>=n)) return;

    int ls=1,ld=nr[unde],m,semn;
    double f;
    for(; ls+1<ld; ) {
        m=(ls+ld)/2;
        if (p[li[unde][m].y].x<p[li[unde][m].y+1].x) semn=1;
        else semn=-1;
        f=(double)semn*(dy[li[unde][m].y]*pct.x+dx[li[unde][m].y]*pct.y+ec[li[unde][m].y]);
        if (f>0) ls=m;
        else if (f<0) ld=m;
        else ls=ld=m;
    }
    m=ls;
    if (p[li[unde][m].y].x<p[li[unde][m].y+1].x) semn=1;
    else semn=-1;
    f=(double)semn*(dy[li[unde][m].y]*pct.x+dx[li[unde][m].y]*pct.y+ec[li[unde][m].y]);
    if(f<0)--m;
    else if(0==f) {
        ++sol;
        return;
    }
    if (p[li[unde][m+1].y].x<p[li[unde][m+1].y+1].x) semn=1;
    else semn=-1;
    f=(double)semn*(dy[li[unde][m+1].y]*pct.x+dx[li[unde][m+1].y]*pct.y+ec[li[unde][m+1].y]);
    if(f>0) ++m;
    else if(0==f) {
        ++sol;
        return;
    }
    if(m%2) ++sol;
}

int main()
{
    ifstream f("poligon.in");
    ofstream g("poligon.out");
    f>>n>>m;
    int i;
    for(i=1; i<=n; ++i) {
        f>>p[i].x>>p[i].y;
        px[i]=p[i].x;
    }
    p[n+1]=p[1];
    sort(px+1,px+n+1);
    for(i=1; i<=n; ++i) {
        dx[i]=p[i+1].x-p[i].x;
        dy[i]=p[i].y-p[i+1].y;
        ec[i]=p[i].x*p[i+1].y-p[i+1].x*p[i].y;
    }
    precalc();
    PER z;
    for(i=1; i<=m; ++i) {
        f>>z.x>>z.y;
        bs(z);
    }
    g<<sol<<'\n';
    return 0;
}