Pagini recente » Cod sursa (job #176580) | Cod sursa (job #1497893) | Cod sursa (job #2057595) | Cod sursa (job #2510564) | Cod sursa (job #1579824)
#include <iostream>
#include <algorithm>
#include <fstream>
#include <iomanip>
#include <vector>
#define INF 999999
#define NMAX 120002
using namespace std;
struct punct
{
double x,y;
}A,Min;
vector<punct> v;
punct stiva[NMAX];
int k,n;
int sens(punct d0,punct d1, punct d2)
{
return ((d1.x-d0.x)*(d2.y-d0.y) - (d2.x-d0.x)*(d1.y-d0.y));
}
int comp(punct a,punct b)
{
return sens(v[1],a,b)<0;
}
int main()
{
ifstream in("infasuratoare.in");
ofstream out("infasuratoare.out");
in >> n;
A.x = INF;
A.y = INF;
v.push_back(A);
for(int i=1;i<=n;i++)
{
in >> A.x >> A.y;
v.push_back(A);
}
Min.y = INF;
for(int i=1;i<=n;i++)
{
if(v[i].y<Min.y)
{
k =i;
Min = v[i];
}
if(v[i].y == Min.y && v[i].x<Min.x)
{
k = i;
Min = v[i];
}
}
swap(v[1],v[k]);
sort(v.begin()+1,v.begin()+n+1,comp);
stiva[1] = v[1];
stiva[2] = v[2];
int varf = 2;
for(int i =3;i<=n;i++)
{
while(varf>=2 && sens(stiva[varf-1],stiva[varf],v[i])>0)
varf--;
stiva[++varf] = v[i];
}
out << fixed;
out << varf << "\n";
for(int i=varf;i>=1;i--)
out << setprecision(9) << stiva[i].x << " " << stiva[i].y << "\n";
return 0;
}