Pagini recente » Cod sursa (job #636219) | Cod sursa (job #1499244)
#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;
double 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)
{
sus.pop_back();
slim--;
}
sus.push_back(v[i]);
jlim=jos.size();
while(jlim>=2 && det(jos[jlim-2],jos[jlim-1],v[i]) <= 0)
{
jos.pop_back();
jlim--;
}
jos.push_back(v[i]);
}
if(jos[0].x==sus[0].x && jos[0].y==sus[0].y)
jos.erase(jos.begin());
if(jos[jos.size()-1].x==sus[sus.size()-1].x && jos[jos.size()-1].y==sus[sus.size()-1].y)
sus.pop_back();
printf("%d\n",jos.size()+sus.size());
for(i=0; i<jos.size(); i++)
printf("%lf %lf\n",jos[i].x,jos[i].y);
for(i=sus.size()-1; i>=0; i--)
printf("%lf %lf\n",sus[i].x,sus[i].y);
}