Pagini recente » Cod sursa (job #1782397) | Cod sursa (job #2932638) | Cod sursa (job #438050) | Cod sursa (job #485112) | Cod sursa (job #2421385)
#include <fstream>
#include <algorithm>
#include <cmath>
#include <iomanip>
#include <iostream>
#define double long double
#define EPS 1e-12
#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;
if(y < 0)
cout << x << ' ' << y << '\n';
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(a.y == b.y)
return a.x < b.x;
return a.y < b.y;
});
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]) <= EPS)
--poz;
st[++poz] = v[i];
}
while(poz > 1 && det(st[poz - 1], st[poz], st[1]) <= EPS)
--poz;
fout << poz << '\n';
for(int i = 1; i <= poz; ++i)
fout << fixed << setprecision(6) << st[i].x + v[1].x << ' ' << st[i].y + v[1].y << '\n';
return 0;
}