Pagini recente » Cod sursa (job #233070) | Cod sursa (job #1343615) | Cod sursa (job #1127555) | Cod sursa (job #1235281) | Cod sursa (job #1920472)
#include <iostream>
#include <fstream>
#include <vector>
#include <algorithm>
#include <iomanip>
using namespace std;
ifstream fin("infasuratoare.in");
ofstream fout("infasuratoare.out");
const int MAX = 120005;
struct punct{
double x,y;
}p[MAX];
int n,vf;
int stiva[MAX];
inline double det(punct a,punct b,punct c){
return (c.x-a.x)*(b.y-a.y)-(c.y-a.y)*(b.x-a.x);
}
inline bool cmp(punct a,punct b){
return det(a,b,p[1])>0;
}
void problema_Initial(){
fin>>n;
int i,poz=1;
for(i=1;i<=n;i++){
fin>>p[i].x>>p[i].y;
if(p[poz].x>p[i].x || (p[poz].x==p[i].x && p[poz].y>p[i].y))
poz=i;
}
swap(p[1],p[poz]);
sort(p+2,p+n+1,cmp);
}
void convex_Hull(){
stiva[++vf]=1;
stiva[++vf]=2;
for(int i=3;i<=n;i++){
while(vf>=2 && det(p[stiva[vf-1]],p[stiva[vf]],p[i])<0)
vf--;
stiva[++vf]=i;
}
}
int main()
{
problema_Initial();
convex_Hull();
fout<<vf<<'\n';
for(int i=vf;i>0;i--)
fout<<setprecision(6)<<fixed<<p[stiva[i]].x<<" "<<p[stiva[i]].y<<'\n';
return 0;
}