# Cod sursa(job #496991)

Utilizator Data 31 octombrie 2010 22:21:40 Infasuratoare convexa 0 cpp done Arhiva educationala 1.87 kb
``````#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;
}

{
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()
{