Pagini recente » Cod sursa (job #1702738) | Cod sursa (job #3171556) | Cod sursa (job #410837) | Cod sursa (job #773985) | Cod sursa (job #3215935)
#include <fstream>
#include <vector>
#include <algorithm>
#include <cmath>
#include <iomanip>
using namespace std;
ifstream in ("infasuratoare.in");
ofstream out ("infasuratoare.out");
struct punct
{
double x, y, polar, dist;
bool start;
}v[120005];
int left_turn (punct a, punct b, punct c)
{
return (a.x * (b.y - c.y) + b.x * (c.y - a.y) + c.x * (a.y - b.y)) >= 0;
}
int n, start_y, start_x, indice;
bool criteriu (punct a, punct b)
{
if (a.start)
return 1;
if (b.start)
return 0;
return a.polar < b.polar || (a.polar == b.polar && a.dist < b.dist);
}
int convex_hull[120005];
int main()
{
in >> n;
start_y = 1e9 + 1;
for (int i = 1; i <= n; i ++)
{
in >> v[i].x >> v[i].y;
if (v[i].y < start_y || (v[i].y == start_y && v[i].x > start_x))
{
start_x = v[i].x;
start_y = v[i].y;
indice = i;
}
v[i].start = false;
}
v[indice].start = true;
for (int i = 1; i <= n; i ++)
if (v[i].start == false)
{
v[i].dist = sqrt((v[indice].x - v[i].x) * (v[indice].x - v[i].x) + (v[indice].y - v[i].y) * (v[indice].y - v[i].y));
if (v[indice].y == v[i].y)
v[i].polar = -2e9;
else v[i].polar = -(v[i].x - v[indice].x) / (v[i].y - v[indice].y);
}
sort (v + 1, v + n + 1, criteriu);
convex_hull[0] = 2;
convex_hull[1] = 1;
convex_hull[2] = 2;
for (int i = 3; i <= n; i ++)
{
while (convex_hull[0] >= 2 && !left_turn(v[convex_hull[convex_hull[0] - 1]], v[convex_hull[convex_hull[0]]], v[i]))
convex_hull[0] --;
convex_hull[0] ++;
convex_hull[convex_hull[0]] = i;
}
out << convex_hull[0] << '\n';
for (int i = 1; i <= convex_hull[0]; i ++)
out << setprecision(6) << fixed << v[convex_hull[i]].x << ' ' << setprecision(6) << fixed << v[convex_hull[i]].y << '\n';
return 0;
}