Pagini recente » Cod sursa (job #1048939) | Monitorul de evaluare | Cod sursa (job #513652) | Cod sursa (job #1377895) | Cod sursa (job #3248035)
#include <iostream>
#include <fstream>
#include <algorithm>
#include <iomanip>
using namespace std;
ifstream f("infasuratoare.in");
ofstream g("infasuratoare.out");
const int NMAX = 120000;
struct punct {
double x, y;
int parte;
} puncte[NMAX + 1];
int n, st[NMAX + 1], k, ck;
bool cmp(punct P1, punct P2)
{
if (P1.x > P2.x)
return false;
if (P1.x == P2.x)
if (P1.y > P2.y)
return false;
return true;
}
double arie (punct P1, punct P2, punct P3)
{
return (P1.x*P2.y + P2.x*P3.y + P3.x*P1.y - P2.y*P3.x - P3.y*P1.x - P1.y*P2.x); /// daca <0 => P3 e sub semiplan
/// daca >0 => P3 e peste semiplan
}
int main()
{
f >> n;
for (int i = 1; i<=n; ++i)
f >> puncte[i].x >> puncte[i].y;
sort(puncte + 1, puncte + n + 1, cmp);
for (int i = 2; i<=n-1; ++i)
if (arie(puncte[1], puncte[n], puncte[i]) < 0)
puncte[i].parte = 1;
else
puncte[i].parte = 2;
st[1] = 1;
k = 1;
for (int i = 2; i<=n; ++i)
if (puncte[i].parte == 1 || puncte[i].parte == 0)
{
while (k>1 && arie(puncte[st[k-1]], puncte[st[k]], puncte[i]) < 0)
--k;
st[++k] = i;
}
ck = k;
st[k] = n;
for (int i = n-1; i>=1; --i)
if (puncte[i].parte == 2 || puncte[i].parte == 0)
{
while (k>ck && arie(puncte[st[k-1]], puncte[st[k]], puncte[i]) < 0)
--k;
st[++k] = i;
}
g << k-1 << '\n';
for (int i = 1; i<=k-1; ++i)
g << fixed <<setprecision(6) << puncte[st[i]].x << ' ' << puncte[st[i]].y << '\n';
return 0;
}