Pagini recente » Cod sursa (job #1421438) | Cod sursa (job #1740875) | Cod sursa (job #2430938) | Cod sursa (job #2491597) | Cod sursa (job #1822116)
#include <iostream>
#include <fstream>
#include <iomanip>
#include <algorithm>
using namespace std;
ifstream in ("infasuratoare.in");
ofstream out ("infasuratoare.out");
class punct{
public:
double x;
double y;
bool operator < (const punct & p)
{
if(x < p.x)
return 1;
else if (x > p.x)
return 0;
if(y<p.y) //daca au abscisele egale sortam dupa y
return 1;
return 0;
}
};
int n;
punct v[121000], stiva[121000];
int vf;
double prod_vectorial(const punct &A, const punct &B, const punct &C)
{
double rez = (B.x - A.x) * (C.y - A.y) - (B.y - A.y) * (C.x - A.x); //cu + e la stanga, cu - e la dreapta
return rez;
}
int cmp (const punct & p1,const punct & p2)
{
int rez = prod_vectorial(v[0], p1, p2) < 0;
return rez;
}
int main()
{
int i;
in>>n;
for(i=0;i<n;++i)
in>>v[i].x>>v[i].y;
int pos = 0;
for (i=1;i<n;++i)
if (v[i] < v[pos])
pos=i; //gasim punctul cel mai "stanga-jos"
swap(v[0], v[pos]);
sort(v + 1, v + n, cmp);
///graham propriu-zis
stiva[0] = v[0];
stiva[1] = v[1];
vf = 1;
for (int i = 2; i < n; ++i)
{
while (vf >= 1 && prod_vectorial(stiva[vf - 1], stiva[vf], v[i]) > 0)
--vf;
++vf;
stiva[vf] = v[i];
}
//afisam in ordine inversa ca se cere ordine trigo
out<< fixed;
out<< vf+1 << "\n";
for (int i = vf; i >= 0; --i)
out << setprecision(9) << stiva[i].x << " " << stiva[i].y << "\n";
in.close();
out.close();
return 0;
}