Pagini recente » Cod sursa (job #2075347) | Cod sursa (job #2560391) | Cod sursa (job #887741) | Cod sursa (job #303135) | Cod sursa (job #1499222)
#include <fstream>
#include <vector>
#include <algorithm>
using namespace std;
#define MAXN 190005
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;
bool det(pc A, pc B, pc C)
{
if((B.x-A.x)*(C.y-A.y) - (C.x-A.x)*(B.y-A.y) > 0)
return 1;
return -1;
}
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]) == 1)
{
slim--;
sus.pop_back();
}
sus.push_back(v[i]);
jlim=jos.size();
while(jlim>=2 && det(jos[jlim-2],jos[jlim-1],v[i]) == -1)
{
jlim--;
jos.pop_back();
}
jos.push_back(v[i]);
}
printf("%d\n",jos.size()+sus.size()-2);
for(i=0; i<jos.size(); i++)
{
pc x =jos[i];
printf("%lf %lf\n",jos[i].x,jos[i].y);
}
for(i=sus.size()-2; i>0; i--)
printf("%lf %lf\n",sus[i].x,sus[i].y);
}