Pagini recente » Cod sursa (job #653744) | Cod sursa (job #2804787) | Cod sursa (job #2038081) | Cod sursa (job #426940) | Cod sursa (job #2214087)
#include <fstream>
#include <algorithm>
#include <iomanip>
using namespace std;
ifstream f("infasuratoare.in");
ofstream g("infasuratoare.out");
int n,i,k,pmin;
struct hh{
double x,y;
};
hh a[120050];
double panta(hh a,hh b)
{
return (b.y-a.y)/(b.x-a.x);
}
bool cmp(hh p,hh t)
{
if(panta(a[1],p)<panta(a[1],t))
return 1;
else
return 0;
}
int s[120050];
int main()
{
f>>n;
f>>a[1].x>>a[1].y;
pmin=1;
for(i=2;i<=n;i++)
{
f>>a[i].x>>a[i].y;
if(a[i].x<a[pmin].x)
pmin=i;
else
if(a[i].x==a[pmin].x)
if(a[i].y<a[pmin].y)
pmin=i;
}
swap(a[pmin],a[1]);
sort(a+2,a+1+n,cmp);
k=2;
s[1]=1;
s[2]=2;
for(i=3;i<=n;i++)
{
if(k==2)
{
k++;
s[k]=i;
}
else
{
while(k>2&&panta(a[s[k-1]],a[i])<panta(a[s[k-1]],a[s[k]]))
k--;
k++;
s[k]=i;
}
}
g<<k<<'\n';
for(i=1;i<=k;i++)
{
g<<setprecision(13)<<fixed<<a[s[i]].x<<" "<<a[s[i]].y<<"\n";
}
return 0;
}