Pagini recente » Cod sursa (job #732300) | Cod sursa (job #2214393) | Cod sursa (job #2586426) | Cod sursa (job #730536) | Cod sursa (job #1161449)
#include <fstream>
#include <iomanip>
#include <algorithm>
using namespace std;
struct punct
{
double x;
double y;
}v[120005];
bool ccw(punct a,punct b,punct c)
{
return (((a.x-b.x)*(c.y-b.y)-(c.x-b.x)*(a.y-b.y))>0.0);
}
punct pivot;
bool operator<(const punct &a,const punct &b)
{
return ccw(a,pivot,b);
}
int main()
{
ifstream cin("infasuratoare.in");
ofstream cout("infasuratoare.out");
int n=0,i;
cin>>n;
cin>>v[1].x>>v[1].y;
pivot=v[1];
int unde=1;
for(i=2;i<=n;i++)
{
cin>>v[i].x>>v[i].y;
if(v[i].x<pivot.x)
pivot=v[i],unde=i;
else if(v[i].x==pivot.x)
if(v[i].y<pivot.y)
pivot=v[i],unde=i;
}
swap(v[unde],v[1]);
if(n)
sort(v+2,v+n+1);
punct stiva[120005];
int poz=0;
stiva[++poz]=v[1];
stiva[++poz]=v[2];
for(i=3;i<=n;i++)
{
while(poz>=2)
if(ccw(stiva[poz-1],stiva[poz],v[i]))
poz--;
else
break;
stiva[++poz]=v[i];
}
cout<<poz<<fixed<<setprecision(6)<<'\n';
for(i=1;i<=poz;i++)
cout<<stiva[i].x<<' '<<stiva[i].y<<'\n';
cin.close();
cout.close();
return 0;
}