Pagini recente » Cod sursa (job #492035) | Clasament dupa rating | Istoria paginii utilizator/ilincat | Cod sursa (job #1639397) | Cod sursa (job #1882076)
#include <fstream>
#include <algorithm>
#include <iomanip>
using namespace std;
ifstream fin("infasuratoare.in");
ofstream fout("infasuratoare.out");
int n,poz,vf,s[120001];
double minx=1000000001,miny=1000000001;
struct punct{
double x,y;}p[120001];
void cit(){
fin>>n;
for(int i=1;i<=n;i++){
fin>>p[i].x>>p[i].y;
if(p[i].y==miny)
if(p[i].x<minx){
minx=p[i].x;
poz=i;}
if(p[i].y<miny){
miny=p[i].y;
minx=p[i].x;
poz=i;}}}
double det(punct p0,punct p1,punct p2){
return (p1.x-p0.x)*(p2.y-p0.y)-(p2.x-p0.x)*(p1.y-p0.y);}
int howtosort(const punct &a,const punct &b){
return det(p[0],a,b)>0;}
void infasuratoare(){
vf=1;
s[0]=0;
s[1]=1;
for(int i=2;i<=n;i++){
while(vf>=1 && det(p[s[vf-1]],p[s[vf]],p[i])<0)
vf=vf-1;
vf=vf+1;
s[vf]=i;}
}
int main(){
cit();
int i;
p[0].x=minx;
p[0].y=miny;
for(i=poz;i<n;i++)
p[i]=p[i+1];
n--;
sort(p+1,p+n+1,howtosort);
infasuratoare();
fout<<vf+1<<'\n';
for(i=0;i<=vf;i++)
fout<<fixed<<setprecision(6)<<p[s[i]].x<<" "<<p[s[i]].y<<'\n';
return 0;}