Pagini recente » Cod sursa (job #2532744) | Cod sursa (job #2276775) | Cod sursa (job #2940933) | Cod sursa (job #20402) | Cod sursa (job #2757321)
/// #include <iostream>
#include <fstream>
#include <algorithm>
#include <iomanip>
#include <vector>
const int SIZE = 130000;
using namespace std;
typedef long double ld;
struct punct
{
ld y, x;
bool operator < (const punct &other) const
{
if(y==other.y) return x<other.x;
return y<other.y;
}
};
ifstream cin("infasuratoare.in");
ofstream cout("infasuratoare.out");
punct v[SIZE];
vector <int> st;
int n;
void readit()
{
cin>>n;
for(int i=1; i<=n; i++)
cin>>v[i].y>>v[i].x;
}
double deter(punct a, punct b, punct c)
{
return a.x*b.y+b.x*c.y+c.x*a.y
-b.y*c.x-a.y*b.x-a.x*c.y;
}
bool cmp(punct a, punct b)
{
return (deter(v[1], a, b)<0);
}
void sortPoints()
{
int ind=1;
for(int i=2; i<=n; i++)
if(!(v[ind]<v[i])) ind=i;
swap(v[1], v[ind]);
sort(v+2, v+n+1, cmp);
}
void convex_hull()
{
sortPoints();
st.push_back(1), st.push_back(2);
for(int i=3; i<=n; i++)
{
while(st.size()>=2 && deter(v[st[st.size()-2]], v[st.back()], v[i])>0)
st.pop_back();
st.push_back(i);
}
}
void afis()
{
cout<<fixed;
cout<<st.size()<<'\n';
for(int i=1; i<st.size(); i++)
cout<<setprecision(9)<<v[st[i]].y<<' '<<v[st[i]].x<<'\n';
cout<<setprecision(9)<<v[1].y<<' '<<v[1].x<<'\n';
}
int main()
{
readit();
convex_hull();
afis();
return 0;
}