Pagini recente » Cod sursa (job #1227701) | Cod sursa (job #1408310) | Cod sursa (job #1859338) | Cod sursa (job #1455356) | Cod sursa (job #2280032)
#include <fstream>
#include <algorithm>
#include <iomanip>
using namespace std;
ifstream cin("infasuratoare.in");
ofstream cout("infasuratoare.out");
int nr, contor;
struct Punct
{
double x, y;
}v[120004], sol[120004];
bool f1(Punct a, Punct b)
{
if(a.x != b.x)
return a.x < b.x;
return a.y < b.y;
}
double determinant(Punct p, Punct a, Punct b)
{
double CP;
CP = (a.x - p.x)*(b.y-p.y)-(b.x*p.x)*(a.y-p.y);
return CP;
}
bool f2(Punct a, Punct b)
{
return determinant(a, b, v[1]) < 0;
}
int main()
{
cin >> nr;
for(int i=1; i <= nr; i++)
{
cin >> v[i].x >> v[i].y;
}
sort(v+1, v+nr+1, f1);
sort(v+2, v+nr+1, f2);
sol[1] = v[1];
sol[2] = v[2];
sol[3] = v[3];
contor = 3;
for(int i=4; i <= nr; i++)
{
while(determinant(sol[contor], v[i], sol[contor-1]) > 0)
contor--;
contor++;
sol[contor] = v[i];
}
cout << contor << '\n';
for(int i=contor; i > 0; i--)
{
cout << fixed << setprecision(13) << sol[i].x << ' ' << sol[i].y << '\n';
}
}