Pagini recente » Cod sursa (job #2281345) | Cod sursa (job #613062) | Cod sursa (job #2488710) | Cod sursa (job #1682926) | Cod sursa (job #2531892)
#include <iostream>
#include <fstream>
#include <cmath>
#include <algorithm>
#include <iomanip>
using namespace std;
ifstream fin("infasuratoare.in");
ofstream fout("infasuratoare.out");
const int DIM = 120005;
int n,head=1;
struct Pair
{
double x,y;
};
Pair v[DIM],Stack[DIM];
void Read()
{
fin>>n;
for(int i=1;i<=n;i++)
fin>>v[i].x>>v[i].y;
}
double Check(Pair a, Pair b, Pair c)
{
return (b.x-a.x)*(c.y-a.y)-(b.y-a.y)*(c.x-a.x);
}
bool Compare(Pair a, Pair b)
{
return Check(v[1],a,b)<0;
}
void Sort()
{
int xMin=0,yMin=0,pos=1;
xMin=v[1].x;
yMin=v[2].y;
for(int i=2;i<=n;i++)
{
if(v[i].x<xMin)
{
xMin=v[i].x;
yMin=v[i].y;
pos=i;
}
else if(v[i].x==xMin)
{
if(v[i].y<yMin)
{
yMin=v[i].y;
pos=i;
}
}
}
swap(v[1],v[pos]);
sort(v+2,v+1+n,Compare);
}
void Convex()
{
Sort();
Stack[1]=v[1];
Stack[2]=v[2];
head=2;
for(int i=3;i<=n;i++)
{
while(head>=2 && Check(Stack[head-1],Stack[head],v[i])>0)
head--;
head++;
Stack[head]=v[i];
}
}
void Show()
{
fout<<head<<'\n';
for(int i=head;i>=1;i--)
fout<<fixed<<setprecision(9)<<Stack[i].x<<" "<<Stack[i].y<<'\n';
}
int main()
{
Read();
Convex();
Show();
}