Pagini recente » Cod sursa (job #2957606) | Cod sursa (job #645368) | Cod sursa (job #2431110) | Cod sursa (job #2623380) | Cod sursa (job #3180458)
#include <iostream>
#include <fstream>
#include <algorithm>
#include <vector>
#include <iomanip>
#define y first
#define x second
using namespace std;
ifstream fin("infasuratoare.in");
ofstream fout("infasuratoare.out");
const int Nmax=120005;
const long double eps = 1e-12;
pair<double,double> a[Nmax];
vector<int> st;
bool viz[Nmax];
bool isright(pair<double,double> c,pair<double,double> a,pair<double,double> b)
{
return ((c.y-a.y)*(b.x-a.x)-(c.x-a.x)*(b.y-a.y)>=eps);
}
int main()
{
int n;
fin>>n;
for(int i=1;i<=n;i++)
{
fin>>a[i].x>>a[i].y;
}
sort(a+1,a+n+1);
st.push_back(1);
st.push_back(2);
viz[2]=1;
int ind=1;
int sgn=1;
for(int i=3;i>0;i+=sgn)
{
if(i==n) sgn=-1;
if(!viz[i])
{
while(isright(a[i],a[st[ind-1]],a[st[ind]]))
{
viz[st[ind]]=0;
st.pop_back();
ind--;
}
st.push_back(i);
ind++;
viz[i]=1;
}
}
fout<<ind<<'\n';
for(int i=0;i<ind;i++)
{
fout<<setprecision(12)<<a[st[i]].x<<' '<<a[st[i]].y<<'\n';
}
return 0;
}