Cod sursa(job #1775899)

Utilizator dcutitoiuCutitoiu Adrian-Nicolae dcutitoiu Data 10 octombrie 2016 19:52:35
Problema Regiuni Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.87 kb
#include <iostream>
#include <fstream>
#include <iterator>
#include <vector>
#include <unordered_set>
#include <bitset>
#include <algorithm>

using namespace std;

/**
 * Algorithm:
 *
 * Step 1: Read the segments and store them.
 * Step 2: Read the points one by one.
 * Step 3: For each point generate a key.
 *         The key is a vector<bool> region where region[i] == 1 if
 *         the current point is above the i-th segment.
 * Step 3: Insert the region into a set of regions.
 * Step 4: Print the number of regions in the set.
 *
 */

struct Point
{
    int x;
    int y;
};

istream & operator>> (istream & in, Point & point)
{
    in >> point.x >> point.y;
    return in;
}

struct Segment
{
    int a;
    int b;
    int c;
};

istream & operator>> (istream & in, Segment & segment)
{
    in >> segment.a >> segment.b >> segment.c;
    return in;
}

// Returns true if the point is above the segment
bool IsAbove(Point point, Segment segment)
{
    return segment.a * point.x + segment.b * point.y + segment.c > 0;
}

ifstream in("regiuni.in");
ofstream out("regiuni.out");

int main()
{
    int numberPoints, numberSegments;
    in >> numberSegments >> numberPoints;

    // Step 1
    vector<Segment> segments(numberSegments);
    copy_n(istream_iterator<Segment>(in), numberSegments, segments.begin());

    // Step 2
    unordered_set<vector<bool>> regions;
    for_each(istream_iterator<Point>(in), istream_iterator<Point>(),
    [&](Point point)
    {
        // Step 3
        vector<bool> region(numberSegments);
        transform(segments.begin(), segments.end(), region.begin(),
        [&](const Segment & segment)
        {
            return IsAbove(point, segment);
        });

        //Step 4
        regions.insert(region);
    });

    // Step 5
    out << regions.size();

    return 0;
}