Pagini recente » Cod sursa (job #3295013) | Cod sursa (job #3269674) | Cod sursa (job #3287702) | Cod sursa (job #3264836) | Cod sursa (job #496991)
Cod sursa(job #496991)
#include <fstream>
#include <vector>
#include <algorithm>
#include <iostream>
#include <iomanip>
using namespace std;
typedef pair<double,double> dot;
vector<dot> v;
double crossProduct(dot p1, dot p2, dot p)
{
dot a = make_pair(p1.first - p.first, p1.second - p.second);
dot b = make_pair(p2.first - p.first, p2.second - p.second);
return a.first * b.second - a.second * b.first;
}
bool turnsRight(dot p1, dot p2, dot p)
{
return crossProduct(p1, p2, p) < 0;
}
vector<dot> convexHull(vector<dot> &points)
{
vector<dot> convexPoints;
sort(points.begin(), points.end());
convexPoints.push_back(points[0]);
convexPoints.push_back(points[1]);
for (int i = 2; i < points.size(); ++i)
{
while (convexPoints.size() > 2 && turnsRight(convexPoints[convexPoints.size() - 2], points[i], convexPoints[convexPoints.size() - 1]))
convexPoints.pop_back();
convexPoints.push_back(points[i]);
}
for (int i = points.size() - 2; i >= 0; --i)
{
while (convexPoints.size() > 2 && turnsRight(convexPoints[convexPoints.size() - 2], points[i], convexPoints[convexPoints.size() - 1]))
convexPoints.pop_back();
convexPoints.push_back(points[i]);
}
convexPoints.pop_back();
return convexPoints;
}
void readPoints(vector<dot> &pointList, string inputFile)
{
fstream f(inputFile.c_str(), ios::in);
int n;
f >> n;
while (n-- > 0)
{
double a, b;
f >> a >> b;
pointList.push_back(make_pair(a,b));
}
}
void printPoints(vector<dot> &pointList, string outputFile)
{
fstream f(outputFile.c_str(), ios::out);
f << pointList.size() << "\n";
for (int i = 0; i < pointList.size(); ++i)
f << pointList[i].first << " " << pointList[i].second << "\n";
}
int main()
{
vector<dot> answer;
readPoints(v, "infasuratoare.in");
answer = convexHull(v);
printPoints(answer, "infasuratoare.out");
return 0;
}