Pagini recente » Cod sursa (job #3356314) | Cod sursa (job #1460973) | Cod sursa (job #1168508) | Cod sursa (job #3313560) | Cod sursa (job #2277423)
#include <iostream>
#include <algorithm>
#include <fstream>
#include <iomanip>
using namespace std;
const int NM=120002;
struct dot{double x,y;} a[NM];
bool tk[NM];
int n,s[NM],l;
ifstream f("infasuratoare.in");
ofstream g("infasuratoare.out");
bool convex(dot A1,dot A2,dot A3)
{
if((A2.x-A1.x)*(A3.y-A1.y)-(A2.y-A1.y)*(A3.x-A1.x)>0.000000000001)return 1;
return 0;
}
bool mere(int i)
{
if(convex(a[s[l-1]],a[s[l]],a[i]))return 1;
return 0;
}
bool sa(dot A,dot B)
{
if(A.x<B.x)return 1;
if(A.x==B.x&&A.y<B.y)return 1;
return 0;
}
int main()
{
f>>n;
for(int i=1;i<=n;++i)f>>a[i].x>>a[i].y;
sort(a+1,a+n+1,sa);
s[1]=1;s[2]=2;tk[2]=1;l=2;
for(int i=1;i<=n;++i)
{
if(!tk[i])
{
while(l>=2&&!mere(i)){tk[s[l]]=0;--l;}
++l;
s[l]=i;tk[i]=1;
}
}
for(int i=n;i>0;--i)
{
if(!tk[i])
{
while(l>=2&&!mere(i)){tk[s[l]]=0;--l;}
++l;
s[l]=i;tk[i]=1;
}
}
--l;
g<<l<<'\n';
g<<setprecision(6)<<fixed;
for(int i=1;i<=l;++i)g<<a[s[i]].x<<' '<<a[s[i]].y<<'\n';
}