Pagini recente » Cod sursa (job #468908) | Cod sursa (job #520587) | Cod sursa (job #2043439) | Cod sursa (job #42834) | Cod sursa (job #1829847)
#include <fstream>
#include <algorithm>
using namespace std;
ifstream fin("infasuratoare.in");
ofstream fout("infasuratoare.out");
int ind;
double det;
int i,j,k,n,prez[120002];
struct punct
{
int ind;
double x,y;
}a[120002],v[120002];
int compare(punct x,punct y)
{
if(x.y!=y.y)
return x.y<y.y;
return x.x<y.x;
}
int main()
{
fin>>n;
for(i=1;i<=n;i++)
fin>>a[i].x>>a[i].y,a[i].ind=i;
sort(a+1,a+n+1,compare);
for(i=1;i<=n;i++)
a[i].ind=i;
v[1]=a[1];
v[2]=a[2];
prez[1]=1;
prez[2]=1;
i=2;
k=2;
while(i<n)
{
i++;
det=v[k-1].x *v[k].y + v[k].x *a[i].y + a[i].x * v[k-1].y - a[i].x * v[k].y - v[k-1].x * a[i].y - v[k].x * v[k-1].y;
while(det>0&&k>2)
{
prez[v[k].ind]=0;
k--;
det=v[k-1].x *v[k].y + v[k].x *a[i].y + a[i].x * v[k-1].y - a[i].x * v[k].y - v[k-1].x * a[i].y - v[k].x * v[k-1].y;
}
k++;
v[k]=a[i];
prez[v[k].ind]=1;
}
while(i>1)
{
i--;
if(prez[a[i].ind]==1)
continue;
det=v[k-1].x *v[k].y + v[k].x *a[i].y + a[i].x * v[k-1].y - a[i].x * v[k].y - v[k-1].x * a[i].y - v[k].x * v[k-1].y;
while(det>0)
{
prez[v[k].ind]=0;
k--;
det=v[k-1].x *v[k].y + v[k].x *a[i].y + a[i].x * v[k-1].y - a[i].x * v[k].y - v[k-1].x * a[i].y - v[k].x * v[k-1].y;
}
k++;
v[k]=a[i];
prez[v[k].ind]=1;
}
fout<<k<<'\n';
fout<<v[1].x<<" "<<v[1].y<<'\n';
for(i=k;i>=2;i--)
fout<<v[i].x<<" "<<v[i].y<<'\n';
return 0;
}