Cod sursa(job #2628574)

Utilizator CraniXortDumitrescul Eduard CraniXort Data 16 iunie 2020 14:07:29
Problema Regiuni Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 2.61 kb
#include <bits/stdc++.h>
#define maxn 1005
#define ld long double

std::ifstream fin ("regiuni.in");
std::ofstream fout ("regiuni.out");

struct Line{
    int a, b, c;
}line[maxn];

struct Point{
    int x, y;
}point[maxn];

bool mat[maxn][maxn];

ld det (ld x1, ld y1, ld x2, ld y2, ld x3, ld y3){
    return (x3-x1) * (y2-y1) - (x2-x1) * (y3-y1);
}

void radixSort (int L, int P, int *order){
    std::vector <int> v[2];
    int i, j, l, p, crt;
    for (l=0; l<L; l++){
        v[0].clear();
        v[1].clear();
        for (i=0; i<P; i++){
            crt = order[i];
            v[mat[crt][l]].push_back (crt);
        }
        for (i=0, j=0; i<v[0].size(); i++, j++)
            order[j] = v[0][i];
        for (i=0; i<v[1].size(); i++, j++)
            order[j] = v[1][i];
    }
}

bool compare (int L, bool *a, bool *b){
    for (int i=0; i<L; i++)
        if (a[i] != b[i])
        return 0;
    return 1;
}

int main()
{
    int L, P, i, j;
    fin >> L >> P;
    for (i=0; i<L; i++)
        fin >> line[i].a >> line[i].b >> line[i].c;
    for (i=0; i<P; i++)
        fin >> point[i].x >> point[i].y;

    long double x1, x2, y1, y2, a, b, c;
    for (int l=0; l<L; l++){
        a = line[l].a;
        b = line[l].b;
        c = line[l].c;
        if (a == 0){
            x1 = 0;
            x2 = 1;
            y1 = y2 = (long double)1.0* (-c) / (b);
        }
        else if (b == 0){
            y1 = 0;
            y2 = 1;
            x1 = x2 = (long double)1.0* (-c) / (a);
        }
        else{
            x1 = 0;
            y1 = (long double)(1.0 * (-c) - a*x1) / b;
            x2 = 1;
            y2 = (long double)(1.0 * (-c) - a*x2) / b;
        }
        if (a*x1+b*y1+c != 0)
            std::cout << "incorect";
        if (a*x2+b*y2+c != 0)
            std::cout << "incorect";

        for (int p=0; p<P; p++){
            if (det (x1, y1, x2, y2, point[p].x, point[p].y) > 0)
                mat[p][l] = true;
            else
                mat[p][l] = false;
        }
    }

    /*
    for (i=0; i<P; i++, fout << '\n')
        for (j=0; j<L; j++)
        fout << mat[i][j] << ' ';
        */


    int order[maxn];
    for (i=0; i<P; i++)
        order[i] = i;

    radixSort (L, P, order);
    //fout <<"\n\n\n";

    /*
    for (i=0; i<P; i++, fout << '\n')
        for (j=0; j<L; j++)
        fout << mat[order[i]][j] << ' ';
        */

    int ans = 1;
    for (i=1; i<P; i++){
        if (compare(L, mat[order[i]], mat[order[i-1]]) == false)
            ans ++;
    }

    fout << ans << '\n';

    return 0;
}