Pagini recente » Cod sursa (job #1311487) | Cod sursa (job #1387128) | Cod sursa (job #1373668) | Cod sursa (job #627606) | Cod sursa (job #1574926)
#include <iostream>
#include <fstream>
#include <algorithm>
#include <iomanip>
using namespace std;
struct punct
{
double x;
double y;
double panta;
};
punct puncte[120001];
punct stiva[120001];
int curent = 2;
int n;
int minx=2000000000, miny = -2000000000,punctales;
bool cmp(punct a,punct b)
{
if (a.panta < b.panta){ return true; }
return false;
}
int main()
{
ifstream in("infasuratoare.in");
ofstream out("infasuratoare.out");
int i;
in >> n;
for (i = 1; i <= n; i++)
{
in >> puncte[i].x;
in >> puncte[i].y;
if (puncte[i].x < minx || (puncte[i].x == minx&&puncte[i].y > miny))
{
minx = puncte[i].x;
miny = puncte[i].y;
punctales = i;
}
}
for (i = 1; i <= n; i++)
{
if (i != punctales&&puncte[i].x == puncte[punctales].x)
puncte[i].panta = -1999999999;
else if (i != punctales)
puncte[i].panta = (puncte[punctales].y - puncte[i].y) / (puncte[punctales].x - puncte[i].x);
else
puncte[i].panta = -2000000000;
}
sort(puncte+1, puncte+n+1, cmp);
stiva[1] = puncte[1];
stiva[2] = puncte[2];
for (i = 3; i <= n; i++)
{
if ((puncte[i].y - stiva[curent - 1].y) * (stiva[curent].x - stiva[curent - 1].x) < (stiva[curent].y - stiva[curent - 1].y) * (puncte[i].x - stiva[curent - 1].x))
{
curent--;
i--;
}
else
{
curent++;
stiva[curent] = puncte[i];
}
}
out << curent << "\n";
for (i = 1; i <= curent; i++)
{
out <<setprecision(9) <<fixed<< stiva[i].x << " " << stiva[i].y << "\n";
}
}