Pagini recente » Cod sursa (job #1085667) | Cod sursa (job #774791) | Cod sursa (job #1834933) | Cod sursa (job #525851) | Cod sursa (job #1728006)
#include <iostream>
#include <fstream>
#include <vector>
#include <algorithm>
#include <stack>
#include <iomanip>
#include <cstdio>
using namespace std;
ifstream fin ("infasuratoare.in");
ofstream fout ("infasuratoare.out");
struct Point
{
double x;
double y;
Point(double x, double y)
{
this->x = x;
this->y = y;
}
};
int n;
Point p0(0,0);
vector<Point> points;
stack<Point> s;
double euclidDistance (Point p1, Point p2)
{
return (p1.x - p2.x) * (p1.x - p2.x) +
(p1.y - p2.y) * (p1.y - p2.y);
}
Point nextToTop (stack<Point>& s)
{
Point p = s.top();
s.pop();
Point p2 = s.top();
s.push(p);
return p2;
}
//2 is counter-clockwise, extracted from the
//formula involving the slope
int orientation(Point p, Point q, Point r)
{
double val = (int)((q.y - p.y) * (r.x - q.x) -
(q.x - p.x) * (r.y - q.y));
if (val == 0)
return 0;
return (val > 0) ? 2:1;
}
bool myfunction(Point p1, Point p2)
{
int o = orientation (p0, p1, p2);
if (o == 0)
return euclidDistance(p0,p1) >= euclidDistance(p1,p2);
return (o == 2)? true:false;
}
void convexHull()
{
//cel mai din stanga si cel mai de jos punct
double ymin = points[0].y;
int min = 0;
for (int i = 1; i < points.size(); i++)
{
if (points[i].y < ymin)
{
ymin = points[i].y;
min = i;
}
else if (points[i].y == ymin && points[i].x < points[min].x)
{
min = i;
}
}
Point p(points[min].x, points[min].y);
points[min].x = points[0].x;
points[min].y = points[0].y;
points[0].x = p.x;
points[0].y = p.y;
p0 = points[0];
sort(points.begin()+1, points.end(), myfunction);
int m = points.size();
/*for (int i = 1; i < points.size(); i++)
{
while (i < (points.size() - 1) && orientation(p0, points[i],points[i+1]) == 0)
i++;
points[m] = points[i];
m++;
}*/
/*if (m < 3)
{
cout<<"cum? "<<"\n";
return;
}*/
// cout<<m<<endl;
s.push(points[0]);
s.push(points[1]);
//for (int i = 0; i < m; i++)
// cout<<points[i].x<<" "<<points[i].y<<endl;
//cout<<endl;
//s.push(points[2]);
for (int i = 2; i < m; i++)
{
while ((s.size() >= 2 )&& orientation(nextToTop(s), s.top(), points[i]) != 2)
s.pop();
s.push(points[i]);
}
//cout<<s.size()<<endl;
}
int main()
{
freopen("infasuratoare.in","r",stdin);
freopen("infasuratoare.out","w",stdout);
cin>>n;
double xi,yi;
for (int i = 1; i <= n; ++i)
{
//int xi,yi;
cin>>xi>>yi;
points.push_back(Point(xi,yi));
}
convexHull();
cout<<fixed;
cout<<setprecision(9)<<s.size()<<"\n";
while (!s.empty())
{
Point aux = s.top();
cout<<aux.x<<" "<<aux.y<<"\n";
s.pop();
}
}