Pagini recente » Cod sursa (job #911477) | Cod sursa (job #1627065) | Cod sursa (job #2440862) | Cod sursa (job #2505924) | Cod sursa (job #2521188)
#include <fstream>
#include <iomanip>
#include <algorithm>
#define maxn 120000
#define INF 1000000000
using namespace std;
ifstream f("infasuratoare.in");
ofstream g("infasuratoare.out");
int n,pctin;
int ST[maxn],p,k;
double X[maxn], Y[maxn];
int IND[maxn];
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]);
}
int main()
{
f>>n;
for(int i=1;i<=n;i++)
f>>X[i]>>Y[i];
pctin=0;
X[0]=INF;
Y[0]=INF;
for(int i=1;i<=n;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[++k]=i;
sort(IND+1, IND+k+1, cmp);
ST[1]=pctin;
p=1;
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;
}