Pagini recente » Cod sursa (job #2044454) | Cod sursa (job #2281584) | Cod sursa (job #2846775) | Cod sursa (job #1462602) | Cod sursa (job #2955483)
#include <fstream>
#include <algorithm>
#include <vector>
#include <iomanip>
#include <cmath>
using namespace std;
const double eps=10e-14;
struct punct{
double x,y;
}v[120005];
int indice=-1;
double cp(punct p1,punct p2,punct p3)
{
return (p2.x-p1.x)*(p3.y-p2.y)-(p2.y-p1.y)*(p3.x-p2.x);
}
int ccw(punct p1,punct p2,punct p3)
{
if(fabs(cp(p1,p2,p3))<eps){return 0;}
if(cp(p1,p2,p3)>=eps){return 1;}
return -1;
}
bool cmp(punct p1,punct p2)
{
return ccw(v[indice],p1,p2)>0;
}
int stiva[120005];
int main()
{
ifstream fin("infasuratoare.in");
ofstream fout("infasuratoare.out");
int n;fin>>n;
for(int i=1;i<=n;i++){
fin>>v[i].x>>v[i].y;
}
int miny=1000000005,minx=1000000005;
for(int i=1;i<=n;i++){
if(v[i].y<miny){
indice=i;miny=v[i].y;minx=v[i].x;
}
else if(v[i].y==miny&&v[i].x<minx){
indice=i;miny=v[i].y;minx=v[i].x;
}
}
swap(v[1],v[indice]);indice=1;
sort(v+2,v+n+1,cmp);
stiva[1]=1;stiva[2]=2;int pozstiva=2;
for(int i=3;i<=n;i++){
while(pozstiva>=2&&ccw(v[stiva[pozstiva-1]],v[stiva[pozstiva]],v[i])<=0){
pozstiva--;
}
pozstiva++;stiva[pozstiva]=i;
}
fout<<pozstiva<<'\n';
for(int i=1;i<=pozstiva;i++){
fout<<fixed<<setprecision(6)<<v[stiva[i]].x<<" ";
fout<<fixed<<setprecision(6)<<v[stiva[i]].y<<'\n';
}
return 0;
}