Pagini recente » Cod sursa (job #2488607) | Cod sursa (job #351454) | Cod sursa (job #176590) | Cod sursa (job #249629) | Cod sursa (job #1497441)
#include <fstream>
#include <vector>
#include <algorithm>
using namespace std;
#define MAXN 120005
struct pc
{
double x,y;
}v[MAXN];
vector<pc> sus,jos;
bool cmp(pc A, pc B)
{
if(A.x==B.x)
return A.y<B.y;
return A.x<B.x;
}
int n,i,slim,jlim;
int det(pc A, pc B, pc C)
{
return (B.x-A.x)*(C.y-A.y) - (C.x-A.x)*(B.y-A.y);
}
int main()
{
freopen("infasuratoare.in","r",stdin);
freopen("infasuratoare.out","w",stdout);
scanf("%d",&n);
for(i=1; i<=n; i++)
scanf("%lf%lf",&v[i].x, &v[i].y);
sort(v+1,v+n+1,cmp);
sus.push_back(v[1]); sus.push_back(v[2]); // det sa fie cu minus
jos.push_back(v[1]); jos.push_back(v[2]); // det sa fie cu plus
for(i=3; i<=n; i++)
{
slim=sus.size();
while(slim>=2 && det(sus[slim-2],sus[slim-1],v[i]) > 0)
{
slim--;
sus.pop_back();
}
sus.push_back(v[i]);
jlim=jos.size();
while(jlim>=2 && det(jos[jlim-2],jos[jlim-1],v[i]) < 0)
{
jlim--;
jos.pop_back();
}
jos.push_back(v[i]);
}
printf("%d\n",jos.size()+sus.size()-2);
for(i=0; i<sus.size(); i++)
printf("%lf %lf\n",sus[i].x,sus[i].y);
for(i=1; i<jos.size()-1; i++)
printf("%lf %lf\n",jos[i].x,jos[i].y);
}