Pagini recente » Cod sursa (job #2470167) | Cod sursa (job #2118226) | Cod sursa (job #647639) | Razvy | Cod sursa (job #953376)
Cod sursa(job #953376)
#include <fstream>
#include <iomanip>
#include <algorithm>
using namespace std;
struct punct
{
double x;
double y;
}v[120005];
double cp(punct a,punct b,punct c)
{
return ((b.x - a.x) * (c.y - a.y) - (b.y - a.y) * (c.x - a.x));
}
punct suport;
bool operator<(const punct &a,const punct &b)
{
return (cp(suport,a,b)<0);
}
#define inf 1000000005.0
int main()
{
ifstream fin("infasuratoare.in");
ofstream fout("infasuratoare.out");
double min_x=inf,min_y=inf;
int n,i;
fin>>n;
for(i=0;i<n;i++)
{
fin>>v[i].x>>v[i].y;
if(v[i].y<min_y)
{
min_y=v[i].y;
min_x=v[i].x;
}
else if(v[i].y==min_y)
if(v[i].x<min_x)
min_x=v[i].x;
}
suport.x=min_x;
suport.y=min_y;
sort(v,v+n);
punct stiva[120005];
int poz=2;
/*
for(i=0;i<n;i++)
cout<<v[i].nume<<'\n';
*/
stiva[0]=v[0];
stiva[1]=v[1];
//cout<<v[n-1].nume<<"asdasd"<<endl;
for(i=2;i<n;i++)
{
while(poz>=2)
if(cp(stiva[poz-2],stiva[poz-1],v[i])>0)
poz--;
else
break;
stiva[poz++]=v[i];
}
fout<<poz<<'\n';
fout<<fixed<<setprecision(6);
for(i=0;i<poz;i++)
{
fout<<stiva[i].x<<' '<<stiva[i].y<<'\n';
}
return 0;
}