Pagini recente » Cod sursa (job #514436) | Cod sursa (job #2479113) | Cod sursa (job #3003997) | Cod sursa (job #2598244) | Cod sursa (job #2421375)
#include <fstream>
#include <algorithm>
#include <cmath>
#include <iomanip>
#define double long double
#define EPS 0.00000000000001
#define NMAX 120005
using namespace std;
ifstream fin("infasuratoare.in");
ofstream fout("infasuratoare.out");
int poz = 3;
struct punct
{
double x, y, unghi;
} v[NMAX], st[NMAX];
double getUnghi(double x, double y)
{
double ung = 0;
ung = atan2(y, x) * 180 / M_PI;
return ung;
}
double det(punct a, punct b, punct c){
return (a.x * b.y + a.y * c.x + b.x * c.y - b.y * c.x - a.y * b.x - a.x * c.y);
}
int main()
{
int n;
fin >> n;
for(int i = 1; i <= n; ++i)
fin >> v[i].x >> v[i].y;
sort(v + 1, v + n + 1, [](punct a, punct b)
{
if(abs(a.x - b.x) < EPS )
return a.y < b.y;
return a.x < b.x;
});
for(int i = 2; i <= n; ++i){
v[i].x -= v[1].x, v[i].y -= v[1].y;
v[i].unghi = getUnghi(v[i].x, v[i].y);
}
sort(v + 2, v + n + 1, [](punct a, punct b)
{
if(abs(a.unghi - b.unghi) < EPS)
return a.y < b.y;
return a.unghi < b.unghi;
});
st[1].x = 0, st[1].y = 0;
st[2] = v[2];
poz = 2;
for(int i = 3; i <= n; ++i){
while(poz > 1 && det(st[poz - 1], st[poz], v[i]) <= 0.0)
--poz;
st[++poz] = v[i];
}
while(poz > 1 && det(st[poz - 1], st[poz], st[1]) <= 0.0)
--poz;
fout << poz << '\n';
for(int i = 1; i <= poz; ++i)
fout << fixed << setprecision(20) << st[i].x + v[1].x << ' ' << st[i].y + v[1].y << '\n';
return 0;
}