Pagini recente » Cod sursa (job #2585819) | Cod sursa (job #26330) | Cod sursa (job #1709380) | Cod sursa (job #3195899) | Cod sursa (job #2168425)
#include <iomanip>
#include <fstream>
#include <algorithm>
#include <cmath>
using namespace std;
ifstream in("infasuratoare.in");
ofstream out("infasuratoare.out");
struct pereche
{
double x,y;
};
pereche v[120005];
pereche stiva[120005];
bool sortare (pereche a ,pereche b)
{
if(a.x<b.x) return true;
if(a.x == b.x)
{
if(a.y < b.y) return true;
return false;
}
return false;
}
bool panta ( pereche a, pereche b)
{
if(atan2(a.y, a.x) > atan2(b.y,b.x) )return true;
return false;
}
double determinant(pereche A, pereche B, pereche C)
{
return (B.x - A.x) * (C.y - A.y) - (B.y - A.y) * (C.x - A.x);
}
int main()
{
int n;
int indice;
pereche reglaj;
reglaj.x = 1000000000;
reglaj.y = 1000000000;
in >> n;
for(int i=1;i<=n;i++)
{
in >> v[i].x >> v[i].y;
if(v[i].x<reglaj.x)
{
reglaj.x = v[i].x;
reglaj.y = v[i].y;
indice = i;
}
else if(v[i].x == reglaj.x && v[i].y < reglaj.y)
{
reglaj.y = v[i].y;
indice = i;
}
}
pereche aux;
aux = v[1];
v[1] = v[indice];
v[indice]=aux;
reglaj = v[1];
for(int i=1;i<=n;i++)
{
v[i].x = v[i].x - reglaj.x;
v[i].y = v[i].y - reglaj.y;
}
sort(v+1,v+n+1,panta);
stiva[1]=v[1];
stiva[2]=v[2];
int vf = 2;
for(int i=3;i<=n;i++)
{
while(determinant(stiva[vf-1], stiva[vf], v[i]) > 0 && vf>=2)
{
vf--;
}
vf++;
stiva[vf] = v[i];
}
out << vf <<"\n";
for(int i=vf;i>=1;i--)
{
out<<fixed;
out<<setprecision(8) << stiva[i].x+reglaj.x <<" "<< stiva[i].y+reglaj.y<<"\n";
}
return 0;
}