Pagini recente » Cod sursa (job #615972) | Cod sursa (job #1698002) | Cod sursa (job #1112929) | Cod sursa (job #2964776) | Cod sursa (job #1006055)
#include <fstream>
#include <iomanip>
#include <algorithm>
#define x first
#define y second
using namespace std;
ifstream fin("infasuratoare.in");
ofstream fout("infasuratoare.out");
typedef pair <double, double> point;
const int INF=120005;
int n,head;
point v[INF],stack[INF];
void read ()
{
fin>>n;
for (int i=1; i<=n; i++)
fin>>v[i].x>>v[i].y;
}
inline double product (point A, point B, point C)
{
return (B.x-A.x)*(C.y-A.y)-(B.y-A.y)*(C.x-A.x);
}
inline int compare (point p1, point p2)
{
return product (v[1],p1,p2)<0;
}
void sort_points ()
{
int k=1;
for (int i=2; i<=n; i++)
{
if (v[i].x<v[k].x)
{
k=i;
}
else if (v[i].x==v[k].x)
{
if (v[i].y<v[k].y)
{
k=i;
}
}
}
swap (v[1],v[k]);
sort (v+2, v+n+1, compare);
}
void convex_hull ()
{
sort_points ();
stack[1]=v[1];
stack[2]=v[2];
head=2;
for (int i=3; i<=n; i++)
{
while (head>=2 && product(stack[head-1],stack[head],v[i])>0)
--head;
stack[++head]=v[i];
}
}
void print ()
{
fout<<fixed;
fout<<head<<"\n";
for (int i=head; i>=1; i--)
{
fout<<setprecision(9)<<stack[i].x<<" "<<stack[i].y<<"\n";
}
}
int main ()
{
read ();
convex_hull ();
print ();
}