Pagini recente » Cod sursa (job #3242236) | Cod sursa (job #549192) | Cod sursa (job #1628990) | Cod sursa (job #2632255) | Cod sursa (job #1606072)
#include <fstream>
#include <algorithm>
#include <iomanip>
using namespace std;
ifstream f("infasuratoare.in");
ofstream g("infasuratoare.out");
long double x[120001],y[120001];
int p,n,i,ind[120001],j,var,st[120001];
bool semn(int i1,int i2,int i3)
{
return (x[i2]-x[i1])*(y[i3]-y[i1])-(y[i2]-y[i1])*(x[i3]-x[i1])<0;
}
bool cmp(int a,int b)
{
return (x[b]-x[p])*(y[a]-y[p])<(x[a]-x[p])*(y[b]-y[p]);
}
int main()
{
f>>n;
x[0]=1<<31-1,y[0]=1<<31-1;
for (i=1;i<=n;i++){
f>>x[i]>>y[i];
if (x[p]>x[i] || (x[p]==x[i] && y[i]<y[p]))
p=i;
}
for (i=1;i<=n;i++)
if (i!=p)
ind[++j]=i;
sort(ind+1,ind+n,cmp);
st[var=1]=p;
for (i=1;i<=n-1;i++){
while(var>=2 && semn(st[var-1],st[var],ind[i]))
var--;
st[++var]=ind[i];
}
g<<var<<'\n';
g<<fixed<<setprecision(12);
for (i=1;i<=var;i++)
g<<x[st[i]]<<' '<<y[st[i]]<<'\n';
return 0;
}