Pagini recente » Cod sursa (job #674855) | Cod sursa (job #363672) | Cod sursa (job #616789) | Cod sursa (job #2802737) | Cod sursa (job #610398)
Cod sursa(job #610398)
#include <fstream>
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
struct Point
{
Point()
{}
Point(const float xx, const float yy) : x(xx), y(yy)
{}
inline const bool operator <(const Point& p) const
{
return this->x < p.x || (this->x==p.x && this->y<p.y);
}
float x,y;
};
double CrossProduct(const Point& O, const Point& p1, const Point& p2)
{
return (p1.x - O.x)*(p2.y - O.y) - (p1.y - O.y)*(p2.x - O.x);
}
int ConvexHull(const vector<Point>& vPoints, vector<Point>& vHull)
{
int n = vPoints.size(), k=0;
vHull.resize(n+2);
for (int i=0; i<n; ++i)
{
while (k>=2 && CrossProduct(vHull[k-2], vHull[k-1], vPoints[i])<=0)
k--;
vHull[k++] = vPoints[i];
}
int start = k+1;
for (int i=n-2; i>=0; --i)
{
while (k>=start && CrossProduct(vHull[k-2], vHull[k-1], vPoints[i])<=0)
k--;
vHull[k++] = vPoints[i];
}
vHull.resize(k);
return k;
}
int main()
{
int n;
vector<Point> vPoints;
vector<Point> vHull;
fstream fin("infasuratoare.in", fstream::in);
fstream fout("infasuratoare.out", fstream::out);
fin >> n;
//cout << n << endl;
for (int i=0; i<n; ++i)
{
float x,y;
fin >> x >> y;
vPoints.push_back(Point(x,y));
//cout << vPoints[i].x << " " << vPoints[i].y << endl;
}
//cout << endl;
sort(vPoints.begin(), vPoints.end());
/*for (int i=0; i<n; ++i)
{
cout << vPoints[i].x << " " << vPoints[i].y << endl;
}
cout << endl;*/
fout << ConvexHull(vPoints, vHull)-1 << "\n";
fout.precision(17);
for (int i=1; i<vHull.size(); ++i)
{
fout << vHull[i].x << " " << vHull[i].y << "\n";
}
//cout << "\n";
fin.close();
fout.close();
return 0;
}