Pagini recente » Cod sursa (job #734030) | Cod sursa (job #1794607) | Cod sursa (job #856076) | Cod sursa (job #91238) | Cod sursa (job #2468938)
#include <cstdio>
#include <vector>
#include <cmath>
#include <algorithm>
using namespace std;
struct Point
{
double x,y;
};
const int NMAX=120000;
vector <Point> r;
Point v[NMAX+5];
bool cmp_y(Point a,Point b)
{
return a.y<b.y;
}
bool cmp_orar(Point a,Point b)
{
return (a.y-v[1].y)*(b.x-v[1].x)<(b.y-v[1].y)*(a.x-v[1].x);
}
int main()
{
freopen("infasuratoare.in","r",stdin);
freopen("infasuratoare.out","w",stdout);
Point temp1,temp2,temp3;
int n,i,m1,m2;
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_y);
sort(v+2,v+n+1,cmp_orar);
r.push_back(v[1]);
r.push_back(v[2]);
for(i=3;i<=n;++i)
{
//r.push_back(v[i]);
temp2=*(r.end()-1);
temp1=*(r.end()-2);
temp3=v[i];
m1=(temp2.y-temp1.y)*(temp3.x-temp2.x);
m2=(temp2.x-temp1.x)*(temp3.y-temp2.y);
while(m1>m2)
{
r.pop_back();
temp2=*(r.end()-1);
temp1=*(r.end()-2);
m1=(temp2.y-temp1.y)*(temp3.x-temp2.x);
m2=(temp2.x-temp1.x)*(temp3.y-temp2.y);
}
r.push_back(v[i]);
}
printf("%d\n",r.size());
for(i=0;i<r.size();++i)
printf("%lf %lf\n",r[i].x,r[i].y);
return 0;
}