Cod sursa(job #220872)

Utilizator RobytzzaIonescu Robert Marius Robytzza Data 13 noiembrie 2008 15:46:33
Problema Poligon Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.69 kb
#include <fstream>
#define inf 0x3f3f3f
#define INFINIT -61000

using namespace std;

int n,m,nrsol;

struct punct
{
    int x,y;
} poli[801],infr[60001];

struct punct2{ int x1,x2,y1,y2;};

struct benzi
{
    int nr;
    int X;
    punct2 sir[1000];
}band[801];
int nr_benzi;

ofstream fout ("poligon.out");
ifstream f("poligon.in");

void citire()
{
    f>>n>>m;
    for(int i=0;i<n;++i)
    {
        f>>poli[i].x>>poli[i].y;
        band[i].X=poli[i].x;
    }
    for(int i=0;i<m;++i)
        f>>infr[i].x>>infr[i].y;
}

bool operator<(benzi a, benzi b)
{
    return a.X<b.X;
}

void creeare()
{
    nr_benzi=n;
    for (int i=0;i<n-1;i++)
        if (band[i].X==band[i+1].X)
        {
            nr_benzi--;
            band[i].X=inf;
        }
        sort(band,band+n);
}

void baga_in_benzi()
{
    for (int i=0;i<nr_benzi-1;i++)
        for (int j=0;j<n;j++)
        {
            if(poli[j].x>band[i+1].X || poli[j+1].x<band[i].X)
                continue;
            band[i].sir[band[i].nr].x1=poli[j].x;
            band[i].sir[band[i].nr].y1=poli[j].y;
            band[i].sir[band[i].nr].x2=poli[j+1].x;
            band[i].sir[band[i].nr++].y2=poli[j+1].y;
        }
}

int cautbinar(punct p)
{
    int st=0,dr=nr_benzi-1,mij;
    while(st<dr)
    {
        mij=(st+dr)/2;
        if(band[mij].X < p.x && band[mij+1].X> p.x)
            return mij;
        if(band[mij].X < p.x)
            st=mij+1;
        else
            dr=mij;
    }
    return 0;
}

void anonim()
{
    for(int i=0;i<m;i++)
    {
        int poz=cautbinar(infr[i]),numara;
        punct aux;
        aux.y=INFINIT;
        aux.x=infr[i].x;
        numara=0;
        for (int j=0;j<band[poz].nr;j++)
        {
            long long det1=band[poz].sir[j].x1*band[poz].sir[j].y2 +
                     band[poz].sir[j].y2*aux.x +
                     band[poz].sir[j].x2*aux.y -
                     aux.x*band[poz].sir[j].y2 -
                     aux.y*band[poz].sir[j].x1 -
                     band[poz].sir[j].x2*band[poz].sir[j].y1;

            long long det2=band[poz].sir[j].x1*band[poz].sir[j].y2 +
                     band[poz].sir[j].y2*infr[i].x +
                     band[poz].sir[j].x2*infr[i].y -
                     infr[i].x*band[poz].sir[j].y2 -
                     infr[i].y*band[poz].sir[j].x1 -
                     band[poz].sir[j].x2*band[poz].sir[j].y1;

            if(det1*det2<0)
                numara++;
        }
        if(numara%2)
            nrsol++;
    }
}

int main()
{
    citire();
    sort(band,band+n);
    creeare();
    baga_in_benzi();
    anonim();
    fout<<nrsol<<endl;
    return 0;
}