Pagini recente » Cod sursa (job #1943586) | Cod sursa (job #1617717) | Cod sursa (job #3214271) | Cod sursa (job #540839) | Cod sursa (job #1636304)
#include <fstream>
#include <iomanip>
#include <algorithm>
#define x first
#define y second
#define nMax 120005
using namespace std;
ifstream fin("infasuratoare.in");
ofstream fout("infasuratoare.out");
typedef pair<double, double> Point;
Point v[nMax];
Point stiva[nMax];
int top, n;
inline double cross_product(const Point& A, const Point& B, const Point& C) {
return (B.x - A.x) * (C.y - A.y) - (B.y - A.y) * (C.x - A.x);
}
inline int cmp(const Point& p1, const Point& p2) {
return cross_product(v[1], p1, p2) < 0;
}
void read()
{
fin>>n;
for(int i=1;i<=n;i++)
fin>>v[i].x>>v[i].y;
}
void sort_points()
{
int poz=1;
for(int i=2;i<=n;i++)
if(v[i]<v[poz])
poz=i;
swap(v[1], v[poz]);
sort(v+2, v+n+1, cmp);
}
void convex()
{
sort_points();
stiva[++top]=v[1];
stiva[++top]=v[2];
for(int i=3;i<=n;i++)
{
while(top>=2 && cross_product(stiva[top-1], stiva[top], v[i])>0)
top--;
stiva[++top]=v[i];
}
}
void write()
{
fout<<fixed;
fout<<top<<'\n';
for(int i=top;i>=1;i--)
fout<<setprecision(9)<<stiva[i].x<<" "<<stiva[i].y<<'\n';
}
int main()
{
read();
convex();
write();
return 0;
}