Pagini recente » Cod sursa (job #734805) | Cod sursa (job #2848013) | Cod sursa (job #667986) | Cod sursa (job #322699) | Cod sursa (job #3195727)
#include <fstream>
#include <iomanip>
#include <vector>
#include <algorithm>
using namespace std;
int n;
struct punct
{
double x, y;
} p[120000];
vector<punct> st;
int pstart()
{
int i1=0;
for(int i=1; i<n; i++)
{
if(p[i].y<p[i1].y || (p[i].y==p[i1].y && p[i].x<p[i1].x))
i1=i;
}
return i1;
}
double orientare(const punct& a, const punct& b, const punct& c)
{
return (b.y-a.y)*(c.x-b.x)-(b.x-a.x)*(c.y-b.y);
}
bool cmp(const punct& a, const punct& b)
{
return orientare(p[0], a, b)<0;
}
void cst()
{
st.push_back(p[0]);
st.push_back(p[1]);
for(int i=2; i<n; i++)
{
while(st.size()>=2 && orientare(st[st.size()-2], st.back(), p[i])>=0)
st.pop_back();
st.push_back(p[i]);
}
}
int main()
{
ifstream cin("infasuratoare.in");
ofstream cout("infasuratoare.out");
cin>>n;
for(int i=0; i<n; i++)
cin>>p[i].x>>p[i].y;
swap(p[0], p[pstart()]);
sort(p+1, p+n, cmp);
cst();
cout<<st.size()<<'\n';
cout << setprecision(6) << fixed;
for(const punct& q : st)
cout<<q.x<<' '<<q.y<<'\n';
return 0;
}