Cod sursa(job #2817017)

Utilizator LicaMihaiIonutLica Mihai- Ionut LicaMihaiIonut Data 12 decembrie 2021 18:22:16
Problema Poligon Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 3.66 kb
#include <stdio.h>
#include <math.h>
#include <stdlib.h>
#include <algorithm>
#include <vector>
#define NMAX 888
#define eps 0.0000001
#define min(a, b) ((a) < (b) ? (a):(b))
#define max(a, b) ((a) > (b) ? (a):(b))

using namespace std;

struct panamea
{
        double m, a, b, c;
}
        A[NMAX][NMAX];

int N, M, Num, V[NMAX];
vector<pair<double, double> > P;
vector<double> PP;
vector<pair<double, double> > pp;

bool operator<(const struct panamea &a, const struct panamea &b)
{
        return (a.m < b.m);
}

double intersect(double k, double x1, double y1, double x2, double y2)
{
        double a = y1-y2, b = x2-x1, c = x1*y2-x2*y1;
        return (-(c+a*k)/b);
}

int main()
{
        int i, j, ok, cate, lo, hi, mij, dubl = 0;
        double x, y, x2, y2, a, b, c, t;

        freopen("poligon.in", "r", stdin);
        scanf("%d %d", &N, &M);

        for (i = 0; i < N; i++)
        {
            scanf("%lf %lf", &x, &y);
            P.push_back(make_pair(x, y));
            pp.push_back(make_pair(x, y));
        }
        P.push_back(make_pair(P[0].first, P[0].second));

        sort(pp.begin(), pp.end());
        j = 1;
        PP.push_back(pp[0].first);
        for (i = 1; i < N; i++)
            if (PP[j-1] != pp[i].first)
               { PP.push_back(pp[i].first); j++; }

        for (i = 0; i < PP.size(); i++)
        {
            for (j = 0; j < N; j++)
            {
                ok = 0;
                x = PP[i];
                if ((P[j].first <= x && P[j+1].first >= x) || (P[j+1].first <= x && P[j].first >= x))
                {ok++; y = intersect(x, P[j].first, P[j].second, P[j+1].first, P[j+1].second); }
                x2 = PP[i+1];
                if ((P[j].first <= x2 && P[j+1].first >= x2) || (P[j+1].first <= x2 && P[j].first >= x2))
                {ok++; y2 = intersect(x2, P[j].first, P[j].second, P[j+1].first, P[j+1].second);}
                if (ok == 2)
                {
                        A[i][ V[i] ].m = (y2+y)/2.0;
                        A[i][ V[i] ].a = y-y2;
                        A[i][ V[i] ].b = x2-x;
                        A[i][ V[i]++ ].c = x*y2-x2*y;
                }
            }
            sort(A[i], A[i]+V[i]);
        }

        for (i = 0; i < M; i++)
        {
                scanf("%lf %lf", &x, &y);
                lo = 0; hi = PP.size()-1;
                ok = -1;
                while (hi-lo >= 0)
                {
                        mij = (hi+lo)>>1;
                        if (PP[mij] >= x) hi = mij-1;
                        else lo = mij+1, ok = mij;
                }
                if (x == PP[0]) ok = 0;
                if (ok < PP.size() - 1 && PP[ok+1] == x) dubl = 1;
                else dubl = 0;
                dubl += ok;
                for(; ok <= dubl; ok++)
                {
                     lo = 0; hi = V[ok]-1;
                     cate = -1;
                     while (hi-lo >= 0)
                     {
                             mij = (lo+hi)>>1;
                             a = A[ok][mij].a; b = A[ok][mij].b; c = A[ok][mij].c;
                             if ((a*x+b*y+c) < -eps) hi = mij-1;
                             else
                                 if ((a*x+b*y+c) > eps) lo = mij+1, cate = mij;
                                 else
                                     cate = 0, lo = 2*(hi+3);
                     }
                     if (cate < V[ok])
                        if ((cate+1)%2 == 1)
						{
							Num++;
							break;
						}
                }
        }

        freopen("poligon.out", "w", stdout);
        printf("%d\n", Num);

        return 0;

}