Cod sursa(job #1257094)

Utilizator Andrei1998Andrei Constantinescu Andrei1998 Data 7 noiembrie 2014 11:11:27
Problema Poligon Scor 100
Compilator cpp Status done
Runda Lista lui wefgef Marime 3.08 kb
#include <fstream>
#include <algorithm>
#include <cmath>
#include <vector>
#include <cstdlib>
#include <ctime>

#define NMAX 805
#define eps 0.000001
using namespace std;

struct point{
    double x,y;
    point(double x=0,double y=0): x(x), y(y) {}
}v[NMAX];
double xs[NMAX];

double s,c;
inline void init_rand(){
    srand(time(0));

    double alpha=((rand()%10000+1)*0.0001)*M_PI;
    //double alpha=0;
    //double alpha=2.78125;

    s=sin(alpha);
    c=cos(alpha);
}

inline void trans(point &x){
    double nx=x.x*c-x.y*s;
    double ny=x.x*s+x.y*c;

    x.x=nx;
    x.y=ny;
}

struct segment{
    point a,b;
    double ym;

    segment(point a=point(),point b=point()): a(a), b(b) {
        ym=((a.y+b.y)*0.5);
    }
};


inline double y_at_x(const segment &s,double x){
    return ((x-s.a.x)*(s.b.y-s.a.y)/(s.b.x-s.a.x)+s.a.y);
}

bool operator<(const segment &a,const segment &b){
    return a.ym<b.ym;
}

class fasie{
public:
    double x0,x1;

    vector<segment> segments;

    fasie(): x0(0), x1(0) {}

    bool inside(const point &x){
        int st=0;
        int dr=segments.size()-1;
        int mijl=(dr>>1);
        int rasp=-1;

        double aux;
        while(st<=dr){
            aux=y_at_x(segments[mijl],x.x);

            if(fabs(aux-x.y)<eps)
                return 1;
            else if(aux<x.y){
                st=mijl+1;
                rasp=mijl;
            }
            else
                dr=mijl-1;

            mijl=(st+dr)>>1;
        }

        return (!(rasp&1));
    }

    void add(const segment &s){
        if(min(s.a.x,s.b.x)<=x0 && x1<=max(s.a.x,s.b.x))
            segments.push_back(segment(point(x0,y_at_x(s,x0)),point(x1,y_at_x(s,x1))));
    }
}fasii[NMAX];

int main()
{
    ifstream cin("poligon.in");
    ofstream cout("poligon.out");

    int n=0,m=0,i,j;
    cin>>n>>m;

    init_rand();
    for(i=1;i<=n;i++){
        cin>>v[i].x>>v[i].y;
        trans(v[i]);

        xs[i]=v[i].x;
    }

    /*for(i=1;i<=n;i++){
        cout<<"i="<<i<<' '<<v[i].x<<' '<<v[i].y<<endl;
    }*/

    sort(xs+1,xs+n+1);
    for(i=1;i<n;i++){
        fasii[i].x0=xs[i];
        fasii[i].x1=xs[i+1];

        for(j=1;j<n;j++)
            fasii[i].add(segment(v[j],v[j+1]));
        fasii[i].add(segment(v[1],v[n]));

        sort(fasii[i].segments.begin(),fasii[i].segments.end());
    }

    /*cout<<"Fasiile sunt:"<<endl;
    for(i=1;i<n;i++){
        cout<<i<<' '<<fasii[i].x0<<' '<<fasii[i].x1<<endl;

        cout<<"Cu continutul:"<<endl;
        for(j=0;j<fasii[i].segments.size();j++)
            cout<<j<<' '<<fasii[i].segments[j].a.x<<' '<<fasii[i].segments[j].a.y<<' '<<fasii[i].segments[j].b.x<<' '<<fasii[i].segments[j].b.y<<endl;
    }*/

    int ans=0;
    point t;

    int poz;
    while(m--){
        cin>>t.x>>t.y;

        trans(t);

        poz=lower_bound(xs+1,xs+n+1,t.x)-xs-1;
        if(!poz)
            continue;

        ans+=fasii[poz].inside(t);
    }

    cout<<ans<<'\n';

    cin.close();
    cout.close();
    return 0;
}