Pagini recente » Cod sursa (job #2965794) | Cod sursa (job #1170962) | Cod sursa (job #363199) | Cod sursa (job #976299) | Cod sursa (job #1580471)
#include <iostream>
#include <algorithm>
#include <fstream>
#include <iomanip>
#include <vector>
#include <utility>
#define INF 999999
#define NMAX 120002
#define x first
#define y second
using namespace std;
typedef pair<double,double> punct;
punct stiva[NMAX],v[NMAX];
int n,pos;
double sens(punct d1,punct d2,punct d3)
{
return ((d2.x-d1.x)*(d3.y-d1.y) - (d3.x-d1.x)*(d2.y-d1.y));
}
bool comp(punct a,punct b)
{
return sens(v[1],a,b)<0;
}
void Sort()
{
pos =1;
for(int i=1;i<=n;i++)
{
if(v[i]<v[pos])
{
pos = i;
}
}
swap(v[1],v[pos]);
sort(v+2,v+n+1,comp);
}
int main()
{
ifstream in("infasuratoare.in");
ofstream out("infasuratoare.out");
in >> n;
for(int i=1;i<=n;i++)
{
in >> v[i].x >> v[i].y;
}
Sort();
int vf = 2;
stiva[1] = v[1];
stiva[2] = v[2];
for(int i=3;i<=n;i++)
{
while(vf>=2 && sens(stiva[vf-1],stiva[vf],v[i])>0)
vf--;
stiva[++vf] = v[i];
}
out << vf <<'\n';
for(int i=vf;i>=1;i--)
{
out << fixed << setprecision(12) << stiva[i].x << " " << stiva[i].y << "\n";
}
return 0;
}