Pagini recente » Cod sursa (job #2198323) | Cod sursa (job #921313) | Cod sursa (job #1949736) | Cod sursa (job #614172) | Cod sursa (job #2981810)
#include <bits/stdc++.h>
using namespace std;
ifstream fin("infasuratoare.in");
ofstream fout("infasuratoare.out");
#define cin fin
#define cout fout
int const N=15e4;
#define float double
#define coord pair<float,float>
coord cord[N];
int n;
double area(coord A,coord B,coord C)
{
double rez=0;
rez+=A.first*B.second;
rez+=B.first*C.second;
rez+=C.first*A.second;
rez-=B.second*C.first;
rez-=C.second*A.first;
rez-=A.second*B.first;
return rez;
}
int Mystack[N];
int rez[N],reznr;
void solveST()
{
int poz=0;
for(int i=0;i<n;i++)
{
while(poz>1 && area(cord[Mystack[poz-2]],cord[Mystack[poz-1]],cord[i])>0)
poz--;
Mystack[poz++]=i;
}
reznr=poz;
for(int i=0;i<poz;i++)
rez[i]=Mystack[i];
}
void solveDR()
{
int poz=0;
for(int i=0;i<n;i++)
{
while(poz>1 && area(cord[Mystack[poz-2]],cord[Mystack[poz-1]],cord[i])<0)
poz--;
Mystack[poz++]=i;
}
for(int i=1;i<poz-1;i++)
rez[reznr+i-1]=Mystack[poz-i-1];
reznr+=poz-2;
}
int main()
{
cin>>n;
for(int i=0;i<n;i++)
{
double x,y;
cin>>x>>y;
cord[i]={x,y};
}
sort(cord,cord+n);
solveST();
solveDR();
cout<<reznr<<'\n';
for(int i=reznr-1;i>-1;i--)
cout<<fixed<<setprecision(6)<<cord[rez[i]].first<<' '<<cord[rez[i]].second<<'\n';
}