Cod sursa(job #902888)

Utilizator otto1Palaga Vicentiu-Octavian otto1 Data 1 martie 2013 17:13:52
Problema Poligon Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 3.04 kb
#include <cstdio>
#include <vector>
#include <string>
#include <bitset>
#include <fstream>
#include <string.h>
#include <math.h>
#include <algorithm>
#define fcat(c) while (c!='\n') fscanf(f,"%c",&c)
#define cat(c) while (c!='\n') scanf("%c",&c)
#define For(i,st,dr,k) for (int i=st;i<=dr;i+=k)
#define ll (long long)
using namespace std;
FILE *f,*g;
struct cp{int x,y;} ax;
cp P[900];
cp a[900]; // muchii x=x1, y=x2
struct cp2{int ind; double ord; } ax2;
vector <int> r[900]; // pe portiuni , unde tin y
cp v[60100];
int n,m;
vector <int> aux;
int mn1,mx1,nn;

void read()
{
    int i;
    ifstream f("poligon.in");
    g=fopen("poligon.out","w");

    f>>n>>m;

    for (i=1;i<=n;i++)
        f>>P[i].x>>P[i].y;
    for (i=1;i<=m;i++)
        f>>v[i].x>>v[i].y;
}

inline double Y(cp P1, cp P2, int x)
{
    return ( (double) ( (double)x-P1.x)*( (double) P2.y-P1.y)/((double) P2.x-P1.x) + P1.y );
}

bool cmp(int x,int y)
{
 //  return (Y(P[x],P[x+1],a[nn].x)+Y(P[x],P[x+1],a[nn].y))<(Y(P[y],P[y+1],a[nn].x)+Y(P[y],P[y+1],a[nn].y));
    return  ( (P[x+1].y-P[x].y)*(double)( (double) a[nn].x+a[nn].y -2*P[x].x)/((double)P[x+1].x-P[x].x)+ 2*P[x].y
           <=(P[y+1].y-P[y].y)*(double)( (double)a[nn].x+a[nn].y -2*P[y].x)/((double)P[y+1].x-P[y].x)+ 2*P[y].y );

}

void pre()
{
    int i,j;

    P[n+1]=P[1];
    for (i=1;i<=n;i++)
        aux.push_back(P[i].x);
    stable_sort(aux.begin(),aux.end());

    nn=0;

    for (i=0;i<=n-2;i++)
    {
        if (aux[i]==aux[i+1]) continue;
        a[++nn].x=aux[i];
        a[nn].y=aux[i+1];

        for (j=1;j<=n;j++)
        {
            if ( (P[j].x<=a[nn].x && a[nn].y<=P[j+1].x) ||
                 (P[j+1].x<=a[nn].x && a[nn].y<=P[j].x) )
                 {
                   // ax2.ord=(double)((double)Y(P[j],P[j+1],a[nn].x)+Y(P[j],P[j+1],a[nn].y))/2;
                   // ax2.ind=j;
                    r[nn].push_back(j);
                 }
        }
        stable_sort(r[nn].begin(),r[nn].end(),cmp);
    }
}

void caut1(int st,int dr,int x)
{
    int m;
    if (st<=dr)
    {
        m=(st+dr)/2;
        if (a[m].x<=x && x<=a[m].y) {mn1=m; return;}
        if (a[m].x>x)
            caut1(st,m-1,x);
        else
            caut1(m+1,dr,x);
    }
}

void caut2(int st,int dr,int x,int y)
{
    int m; double cr;
    if (st<=dr)
    {
        m=(st+dr)/2;
        cr=Y(P[r[mn1][m]],P[r[mn1][m]+1],x);
        if (cr==y) {mx1=0; return ;}
        if (cr<y)
        {
            if (mx1==-1 || mx1<m) mx1=m;
            caut2(m+1,dr,x,y);
        }
        else
            caut2(st,m-1,x,y);

    }

}

void solve()
{
    int i,sol=0;

    for (i=1;i<=m;i++)
    {
        if (v[i].x<a[1].x) continue;
        mn1=-1;
        caut1(1,nn,v[i].x);
        if (mn1==-1) continue;
        mx1=-1;
        caut2(0,r[mn1].size()-1,v[i].x,v[i].y);
        if (mx1==-1) continue;
        if (mx1%2==0) sol++;
    }
    fprintf(g,"%d",sol);

}

int main()
{
    read();
    pre();
    solve();

    return 0;
}