Pagini recente » Cod sursa (job #2607083) | Cod sursa (job #305125) | Cod sursa (job #2559102) | Cod sursa (job #1984679) | Cod sursa (job #2128978)
#include <iostream>
#include <fstream>
#include <algorithm>
#include<iomanip>
using namespace std;
ifstream fin("infasuratoare.in");
ofstream fout("infasuratoare.out");
int n,i,j,k;
struct punct
{
double x;
double y;
};
double determinant(punct a, punct b, punct c)
{
return ((a.x*b.y)+(b.x*c.y)+(a.y*c.x)-(b.y*c.x)-(a.x*c.y)-(b.x*a.y));
}
punct P[120003],S[120003];
bool comp(punct i, punct j)
{
if (determinant(P[1],i,j)>0) return true;
return false;
}
int main()
{
fin>>n;
fin>>P[1].x>>P[1].y;
j=1;
for(i=2;i<=n;++i)
{
fin>>P[i].x>>P[i].y;
if(P[i].x<P[j].x||(P[i].x==P[j].x&&P[i].y<P[j].y))j=i;
}
swap(P[1],P[j]);
sort(P+2,P+1+n,comp);
S[1]=P[1];
S[2]=P[2];
k=2;
for(i=3;i<=n;++i)
{
while(determinant(S[k-1],S[k],P[i])<0)k--;
++k;
S[k]=P[i];
}
fout<<k<<'\n';
fout<<fixed;
for(i=1;i<=k;++i)
{
fout<<setprecision(6)<<S[i].x<<' '<<setprecision(6)<<S[i].y;
fout<<'\n';
}
return 0;
}