Pagini recente » Cod sursa (job #2125191) | Cod sursa (job #766220) | Cod sursa (job #1918603) | Cod sursa (job #2221492) | Cod sursa (job #1775899)
#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;
}