Pagini recente » Cod sursa (job #2360097) | Cod sursa (job #2008564) | Cod sursa (job #2023286) | Cod sursa (job #1883863) | Cod sursa (job #1109344)
#include <algorithm>
#include <fstream>
#include <iomanip>
#include <vector>
#define x first
#define y second
using namespace std;
ifstream f("infasuratoare.in");
ofstream g("infasuratoare.out");
typedef pair<double, double> Point;
Point pMin;
double turns(Point p0, Point p1, Point p2){
return (p1.x - p0.x) * (p2.y - p0.y) - (p2.x - p0.x) * (p1.y - p0.y);
}
int cmp(Point p1, Point p2) {
return turns(pMin, p1, p2) < 0;
}
std::vector<Point> convexHull(std::vector<Point> points)
{
std::vector<Point> convexhull;
uint pmin = 0;
for(uint i = 0; i < points.size(); i++){
if(points[i].y < points[pmin].y){
pmin = i;
}
}
swap(points[0], points[pmin]);
pMin = points[0];
sort(++(points.begin()), points.end(), cmp);
convexhull.push_back(points[0]);
convexhull.push_back(points[1]);
for (uint i = 2; i < points.size(); ++i)
{
while (convexhull.size()>=2 && turns(convexhull[convexhull.size() - 2],
convexhull[convexhull.size() -1],
points[i])>0 )
convexhull.pop_back();
convexhull.push_back(points[i]);
}
return convexhull;
}
std::vector<Point> read()
{
int N;
f>>N;
std::vector<Point> points;
for (uint i = 0; i < N; ++i)
{
double x, y;
f>>x>>y;
Point p;
p.x = x;
p.y = y;
points.push_back(p);
}
return points;
}
void printP(std::vector<Point> points){
g<<fixed<<setprecision(9)<<points.size()<<'\n';
for (int i=0; i < points.size(); i++)
g<<points[i].x<<' '<<points[i].y<<'\n';
}
int main()
{
printP(convexHull(read()));
return 0;
}