Pagini recente » Cod sursa (job #2904035) | Cod sursa (job #501306) | Cod sursa (job #2824399) | Cod sursa (job #2855389) | Cod sursa (job #1331702)
#include <iostream>
#include <fstream>
#include <algorithm>
#include <iomanip>
using namespace std;
ifstream ka("infasuratoare.in");
ofstream ki("infasuratoare.out");
const int N_MAX = 120000;
int n, nr;
struct punct
{
double x, y;
bool operator < (const punct arg) const
{
if(y == arg.y)
return x < arg.x;
else
return y < arg.y;
}
}puncte[N_MAX + 1], raspuns[N_MAX + 1];
double cross_product(punct a, punct b, punct c)
{
return (b.x - a.x) * (c.y - a.y) - (b.y - a.y) * (c.x - a.x);
}
bool comp(punct a, punct b)
{
return cross_product(puncte[1], a, b) < 0;
}
void sortare()
{
int poz = 1;
for(int i = 1; i <= n; i++)
if(puncte[i] < puncte[poz])
poz = i;
swap(puncte[1], puncte[poz]);
sort(puncte + 2, puncte + n + 1, comp);
}
int main()
{
ka >> n;
for(int i = 1; i <= n; i++)
ka >> puncte[i].x >> puncte[i].y;
sortare();
raspuns[1] = puncte[1];
raspuns[2] = puncte[2];
nr = 2;
for (int i = 3; i <= n; ++i)
{
while (nr >= 2 && cross_product(raspuns[nr - 1], raspuns[nr], puncte[i]) > 0)
nr--;
raspuns[++nr] = puncte[i];
}
ki << fixed;
ki << nr << '\n';
for (int i = nr; i >= 1; i--)
ki << setprecision(9) << raspuns[i].x << " " << raspuns[i].y << '\n';
}