Pagini recente » Istoria paginii runda/crrr3 | Cod sursa (job #2059319) | Cod sursa (job #532563) | Cod sursa (job #424174) | Cod sursa (job #1029298)
#include <fstream>
#include <algorithm>
using namespace std;
struct punct
{
double x,y;
}v[120005];
double ccp(punct a,punct b,punct c)
{
return (a.x-b.x)*(c.y-b.y)-(a.y-b.y)*(c.x-b.x);
}
punct centru;
bool operator<(const punct &a,const punct &b)
{
return (ccp(a,centru,b)>0);
}
int main()
{
ifstream cin("infasuratoare.in");
ofstream cout("infasuratoare.out");
centru.x=1000000005;
centru.y=1000000005;
int n,i,unde;
cin>>n;
for(i=0;i<n;i++)
{
cin>>v[i].x>>v[i].y;
if(v[i].x<centru.x)
centru=v[i],unde=i;
else if(v[i].x==centru.x)
if(v[i].y<centru.y)
centru=v[i],unde=i;
}
swap(v[0],v[unde]);
sort(v+1,v+n);
// cout<<"aici"<<endl;
// for(i=0;i<n;i++)
// {
// cout<<v[i].x<<' '<<v[i].y<<endl;
// }
//cout<<"HJOP"<<endl;
punct stiva[120005];
int poz=-1;
stiva[++poz]=v[0];
stiva[++poz]=v[1];
for(i=2;i<n;i++)
{
while(poz>0)
if(ccp(stiva[poz-1],stiva[poz],v[i])>=0)
poz--;
else
break;
stiva[++poz]=v[i];
}
cout<<poz+1<<'\n';
for(i=0;i<=poz;i++)
cout<<stiva[i].x<<' '<<stiva[i].y<<'\n';
cin.close();
return 0;
}