Pagini recente » Cod sursa (job #1069108) | Cod sursa (job #2174951) | Cod sursa (job #2803761) | Cod sursa (job #1842005) | Cod sursa (job #3277852)
#include<iostream>
#include<fstream>
#include<algorithm>
#include<iomanip>
using namespace std;
const int NMAX=120001;
ifstream fin("infasuratoare.in");
ofstream fout("infasuratoare.out");
struct punct
{
double x,y;
};
int n,nrp;
punct p[NMAX], st[NMAX];
double det(const punct &a,const punct &b,const punct &c)
{
return (a.x-b.x)*(b.y-c.y)-(a.y-b.y)*(b.x-c.x);
}
bool compd(const punct &a, const punct &b)
{
return det(p[1],a,b)>0;
}
bool compx(const punct &a, const punct &b)
{
if(a.x==b.x) return a.y<b.y;
return a.x<b.x;
}
void citire()
{
fin>>n;
int pmin=1;
for(int i=1; i<=n; i++)
{
fin>>p[i].x>>p[i].y;
if(compx(p[i],p[pmin]))
pmin=i;
}
swap(p[1],p[pmin]);
}
void graham()
{
sort(p+2,p+n+1,compd);
st[1]=p[1];
st[2]=p[2];
nrp=2;
for(int i=3; i<=n; i++)
{
while(nrp>=2&&det(st[nrp-1],st[nrp],p[i])<0)
nrp--;
st[++nrp]=p[i];
}
}
void afisare()
{
fout<<nrp<<'\n';
fout<<fixed<<setprecision(6);
for(int i=1; i<=nrp; i++)
fout<<st[i].x<<' '<<st[i].y<<'\n';
}
int main()
{
citire();
graham();
afisare();
fin.close();
fout.close();
return 0;
}