Pagini recente » Cod sursa (job #2836560) | Cod sursa (job #1654354) | Cod sursa (job #353702) | Cod sursa (job #2494193) | Cod sursa (job #2520457)
#include <fstream>
#include <algorithm>
#include <iomanip>
#define maxn 120000
#define INF 1000000000
using namespace std;
ifstream f("infasuratoare.in");
ofstream g("infasuratoare.out");
double X[maxn], Y[maxn];
int ST[maxn], IND[maxn], pctin,l, n,p;
bool cmp(int a, int b)
{
return (X[a]-X[pctin]) * (Y[b]-Y[pctin]) > (Y[a]-Y[pctin]) * (X[b]-X[pctin]);
}
double semn(int i1, int i2, int i3)
{
return (X[i1]*Y[i2] + X[i2]*Y[i3] + X[i3]*Y[i1] - X[i3]*Y[i2] - X[i1]*Y[i3] - X[i2]*Y[i1])/2;
}
int main()
{
f>>n;
X[0]=INF;
Y[0]=INF;
pctin=0;
for(int i=1;i<=n;i++)
{
f>>X[i]>>Y[i];
if(Y[i] < Y[pctin])
pctin=i;
else
if(Y[i]==Y[pctin])
if(X[i]<X[pctin])
pctin=i;
}
for(int i=1;i<=n;i++)
if(i!=pctin)
IND[++l]=i;
sort(IND+1, IND+n, cmp);
p=1;
ST[1]=pctin;
for(int i=1;i<=n-1;i++)
{
while(p>=2 and semn(ST[p-1], ST[p], IND[i])<0)
p--;
ST[++p]=IND[i];
}
g<<p<<'\n';
for(int i=1;i<=p;i++)
g<<fixed<<setprecision(6)<<X[ST[i]]<<" "<<Y[ST[i]]<<'\n';
f.close();
g.close();
return 0;
}