Pagini recente » Cod sursa (job #293758) | Cod sursa (job #707913) | Cod sursa (job #843418) | Cod sursa (job #1294019) | Cod sursa (job #2284271)
#include <bits/stdc++.h>
#define Lmax 120002
using namespace std;
ifstream fin("infasuratoare.in");
ofstream fout("infasuratoare.out");
struct punct
{
int x,y;
} a[Lmax],s[Lmax];
int n,i,k;
bool cmp(punct a, punct b)
{
if(a.x < b.x || (a.x == b.x && a.y < b.y)) return true;
return false;
}
int det(punct a,punct b, punct c)
{
if((a.x-c.x)*(b.y-c.y)-(b.x-c.x)*(a.y-c.y)>=0)
return 1;
return 0;
}
int main()
{
fin>>n;
for (i=1; i<=n; i++)
fin>>a[i].x>>a[i].y;
sort(a+1,a+n+1,cmp);
s[1]=a[1];
k=1;
for (i=2; i<=n; i++)
{
while (k>1&&!det(s[k-1],s[k],a[i]))
k--;
k++;
s[k]=a[i];
}
for (i=n-1; i>=1; i--)
{
while (!det(s[k-1],s[k],a[i]))
k--;
k++;
s[k]=a[i];
}
fout<<setprecision(6)<<fixed;
fout<<k-1<<"\n";
for(i=1; i<=k-1; i++) fout<<s[i].x<<" "<<s[i].y<<"\n";
return 0;
}