Cod sursa(job #903631)

Utilizator mipsPavel Mircea mips Data 1 martie 2013 23:47:10
Problema Poligon Scor 60
Compilator cpp Status done
Runda Arhiva de probleme Marime 4.67 kb
#include <iostream>
#include <set>
#include <algorithm>
#include <fstream>
#include <vector>
#include <map>
#include <math.h>
using namespace std;
//ifstream fin("move.in");
ifstream fin("poligon.in");
ofstream fout("poligon.out");



vector<long long> mp;
vector<long long> mpval;
#define PI 3.141592653589793
#define EPS 0.00001
#define INVEPS 100000LL
#define FOR(i,n) for (int i = 0 ; i< n;i++)
#define FORI(i,s,e) for (int i = s ; i<= e;i++)
#define MP(x,y) make_pair(x,y)
#define PB(x) push_back(x)
#define ALL(x) x.begin(),x.end()
#define PDD pair<double,double>
#define X(p) p.first
#define Y(p) p.second
#define NPO make_pair(-1<<20,-1<<20)
#define MPEQ(x,y) ((x.first == y.first)&&(x.second == y.second))
#define SZ(p) p.size()
const int oo = 1<<20;
PDD intersect(pair<PDD,PDD> s1,pair<PDD,PDD> s2)
{
   PDD res;
   PDD a = s1.first;PDD b = s1.second;
   PDD c = s2.first;PDD d = s2.second;
   double di = (X(a) - X(b))*(Y(c) - Y(d)) - (X(c) - X(d))*(Y(a) - Y(b));
   if (di==0)
    return NPO;
   double p1 = (X(a)*Y(b) - X(b)*Y(a)), p2 = (X(c)*Y(d) - X(d)*Y(c));

   X(res) = (p1*(X(c)-X(d)) - p2*(X(a)-X(b)))/di;
   Y(res) = (p1*(Y(c)-Y(d)) - p2*(Y(a)-Y(b)))/di;

   if ((X(res)+EPS>=min(X(a),X(b))) &&
      (X(res)-EPS<=max(X(a),X(b))) &&
      (X(res)+EPS>=min(X(c),X(d))) &&
      (X(res)-EPS<=max(X(c),X(d))) &&
      (Y(res)+EPS>=min(Y(a),Y(b))) &&
      (Y(res)-EPS<=max(Y(a),Y(b))) &&
      (Y(res)+EPS>=min(Y(c),Y(d))) &&
      (Y(res)-EPS<=max(Y(c),Y(d))))
      return res;
    return NPO;
}
double panta(PDD a, PDD b)
{
    if (X(b)-X(a)==0)
    return 0;
    else
    return (Y(b)-Y(a))/(X(b)-X(a));
}

int main()
{

    int n;
    int m;
    int total = 0;
    double rad;
    fin >> n >> m;


    vector< PDD > poli;
    vector< PDD > polic;
    vector< PDD > infr;
    vector< PDD > fasii;

    FOR(i,n)
    {
        int x,y;
        fin >> x >>y;
        poli.PB(MP(x,y));
        polic.PB(MP(x,y));
    }

    FOR(i,m)
    {
        int x,y;
        fin >> x >>y;
        bool in=false;
        FOR(j,n)
            if (MPEQ(MP(x,y),poli[j]))
                in=true;
        if (!in)
            infr.PB(MP(x,y));
        else
            total++;
    }
    sort(ALL(polic));

    FOR(i,n-1)
    if (polic[i].first!=polic[i+1].first)
    {
        //cout << polic[i].first << endl;
        fasii.PB(MP(polic[i].first,polic[i+1].first));
    }
    poli.PB(poli[0]);
    //cout << "---------------------" << endl;
    vector< PDD > psPan[801];

    FOR(i,SZ(fasii))// fiecare fasie
    {

    FOR(j,n)//fiecare latura
    {
        PDD ps = intersect(MP(MP(fasii[i].first,-oo),MP(fasii[i].first,+oo)),MP(poli[j],poli[j+1]));

        PDD pj = intersect(MP(MP(fasii[i].second,-oo),MP(fasii[i].second,+oo)),MP(poli[j],poli[j+1]));

        if (!MPEQ(ps,NPO)&&!MPEQ(pj,NPO))
        {
         //   cout << "intre: " << fasii[i].first <<" si "<< fasii[i].second <<endl;
         //   cout << "latura: " << j <<endl;
         //   cout << "pct intersectie: " << X(ps) <<" "<< Y(ps)<<endl;
         //   cout << "pct intersectie: " << X(pj) <<" "<< Y(pj)<<endl;
//            cout << "adaug"<< Y(ps)<< " " << Y(pj) <<" pt fasia "<< i <<endl;

            psPan[i].PB(MP(Y(ps),panta(ps,pj)));
        }
    }
        sort(ALL(psPan[i]));
    }

    //FOR(i,SZ(fasii))
    //cout << X(fasii[i]) <<" "<<Y(fasii[i])<<endl;


    FOR(i,SZ(infr))
    {
        PDD p=infr[i];
        int poz,poz2,step;

        for (step = 1 ; step < SZ(fasii) ; step<<=1) ;

        for (poz = 0 ; step ; step>>=1)
            if ((poz+step<SZ(fasii)) && X(fasii[step+poz])<=X(p))
                poz+=step;

        //cout << "fasie:" <<X(fasii[poz])<<"-"<<Y(fasii[poz])<<endl;

        for (step = 1 ; step < SZ(psPan[poz]) ; step<<=1) ;
        //cout << "step:" << step<<endl;


        for (poz2 = 0 ;  ; step>>=1)
        {
            //cout << "caut:" << Y(p)<<endl;
            //cout << "pozitie:"<< step+poz2<<endl;
            //cout << "start:"<< psPan[poz][step+poz2].first<<" additional: "<< psPan[poz][step+poz2].second*(X(p)-X(fasii[poz]) )<<endl;
            double comp = psPan[poz][step+poz2].first+psPan[poz][step+poz2].second*(X(p)-X(fasii[poz]) );
            if ((poz2+step<SZ(psPan[poz])) &&  (comp-EPS <= Y(p)))
            {
                if (fabs(comp-Y(p))<EPS)
                {
                    //cout << "small dif"<<endl;
                    poz2=0;
                    break;
                }
                poz2+=step;
            }
            else
            {
                if (poz2+step==0)
                {
                    poz2=1;
                    break;
                }
            }
            if (!step) break;
        }
        total+=1-(poz2%2);
        //cout << 1-(poz2%2) <<endl;
    }
    fout << total;
}