Pagini recente » Cod sursa (job #228800) | Cod sursa (job #947552) | Cod sursa (job #1578588) | Cod sursa (job #1324544) | Cod sursa (job #1154730)
#include <fstream>
#include <algorithm>
#include <cmath>
#include <iomanip>
using namespace std;
struct Point
{
double x, y;
};
Point v[120001], st[120001];
double p1, p2;
int n, i, min1, sf;
bool cmp(const Point A, const Point B)
{
p1=(A.y-v[0].y)/(A.x-v[0].x);
p2=(B.y-v[0].y)/(B.x-v[0].x);
if(A.x==v[0].x)
{
p1=10000;
if(A.y==v[0].y) p1=10001;
}
if(B.x==v[0].x)
{
p2=10000;
if(B.y==v[0].y) p2=10001;
}
return p1>p2;
}
double tri(Point a, Point b, Point c)
{
return a.x*b.y+b.x*c.y+c.x*a.y-a.y*b.x-b.y*c.x-c.y*a.x;
}
int main()
{
ifstream in ("infasuratoare.in");
ofstream out ("infasuratoare.out");
in>>n;
v[0].x=100000;
for(i=1; i<=n; ++i)
{
in>>v[i].x>>v[i].y;
if(v[i].x<v[0].x)
{
v[0].x=v[i].x;
v[0].y=v[i].y;
min1=i;
}
if(fabs(v[i].x-v[0].x)<=0.00000001)
{
if(v[0].y>v[i].y)
{
v[0].y=v[i].y;
min1=i;
}
}
}
sort(v+1, v+n+1, cmp);
sf=2;
st[1]=v[1];
st[2]=v[2];
for(i=3; i<=n; ++i)
{
while(tri(st[sf], st[sf-1], v[i])<=0&&sf>=2)
{
sf--;
}
if(sf==1)
{
sf++; goto p;
}
sf++;
st[sf]=v[i];
p: ;
}
out<<sf<<"\n";
out<<setprecision(6)<<fixed;
out<<st[1].x<<" "<<st[1].y<<"\n";
for(i=sf; i>=2; --i)
{
out<<setprecision(6)<<fixed;
out<<st[i].x<<" "<<st[i].y<<"\n";
}
in.close();
out.close();
return 0;
}