Cod sursa(job #2102695)

Utilizator refugiatBoni Daniel Stefan refugiat Data 9 ianuarie 2018 12:57:05
Problema Poligon Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.89 kb
#include <iostream>
#include <fstream>
#include <algorithm>
#include <vector>
#define x first
#define y second
using namespace std;
ifstream si("poligon.in");
ofstream so("poligon.out");
pair<int,int> p[805];
vector<int> v[805];
int t[805];
long double mij;
int col;
long long det(pair<int,int> a,pair<int,int> b,pair<int,int> c)
{
    return 1LL*a.x*b.y+1LL*b.x*c.y+1LL*c.x*a.y-1LL*a.x*c.y-1LL*b.x*a.y-1LL*c.x*b.y;
}
long double eval(pair<int,int> a,pair<int,int> b,double x)
{
    return a.y+(b.y-a.y)*(mij-a.x)/((double)b.x-a.x);
}
bool cmp(int a,int b)
{
    return eval(p[a],p[a+1],mij)<eval(p[b],p[b+1],mij);
}
bool ok(int i,pair<int,int> a)
{
    long long tmp=det(min(p[i],p[i+1]),max(p[i],p[i+1]),a);
    if(tmp==0)
    {
        col=1;
        return 1;
    }
    return tmp>0;
}
int main()
{
    int n,m;
    si>>n>>m;
    for(int i=1;i<=n;++i)
    {
        si>>p[i].x>>p[i].y;
        t[i]=p[i].x;
    }
    p[n+1]=p[1];
    t[0]=-1;
    sort(t+1,t+n+1);
    int k=0;
    for(int i=1;i<=n;++i)
    {
        if(t[k]!=t[i])
        {
            t[++k]=t[i];
        }
    }
    t[k+1]=t[k]+100;
    for(int i=1;i<=k;++i)
    {
        for(int j=1;j<=n;++j)
        {
            if((p[j].x<=t[i]&&t[i+1]<=p[j+1].x)||(p[j+1].x<=t[i]&&t[i+1]<=p[j].x))
                v[i].push_back(j);
        }
        mij=0.5*(t[i]+t[i+1]);
        sort(v[i].begin(),v[i].end(),cmp);
    }
    int r=0;
    for(int i=1;i<=m;++i)
    {
        pair<int,int> q;
        si>>q.x>>q.y;
        int pos=0;
        for(int pas=1<<9;pas;pas>>=1)
            if(pos+pas<=k&&t[pos+pas]<q.x)
                pos+=pas;
        int rez=-1;
        col=0;
        for(int pas=1<<9;pas;pas>>=1)
            if(rez+pas<v[pos].size()&&ok(v[pos][rez+pas],q))
                rez+=pas;
        ++rez;
        r+=(rez&1)||col;
    }
    so<<r<<'\n';
    return 0;
}