Pagini recente » Cod sursa (job #1855142) | Cod sursa (job #2942506) | Cod sursa (job #3286386) | Cod sursa (job #133508) | Cod sursa (job #1550433)
#include <iostream>
#include <fstream>
#include <iomanip>
#include <cstdlib>
#include <algorithm>
#define nmax 120001
#define inf (1<<30)
#define E 0.000000000001
using namespace std;
struct point {
double x, y;
} AUX[nmax], P[nmax];
int n, s, stSize;
int st[nmax];
bool viz[nmax];
double swX, swY, seX, seY, neX, neY, nwX, nwY;
bool cmp(point a, point b)
{
if (a.y == b.y)
return a.x < b.x;
return a.y < b.y;
}
void init()
{
swX = swY = seY = nwX = inf;
seX = neX = neY = nwY = -inf;
}
void process(int x, int y)
{
if (x < swX || y < swY)
swX = x, swY = y;
if (x > seX || y < seY)
seX = x, seY = y; // South East X - dirty minded
if (x > neX || y > neY)
neX = x, neY = y;
if (x < nwX || y > nwY)
nwX = x, nwY = y;
}
bool checkIfInside(int x, int y)
{
if ((x > swX && x > nwX && x < seX && x < neX) && (y > swY && y < nwY && y > seY && y < neY))
return true;
return false;
}
double det(point A, point B, point C)
{
return A.x*(B.y-C.y) + B.x*(C.y-A.y) + C.x*(A.y-B.y);
}
int main()
{
ifstream fi("infasuratoare.in");
ofstream fo("infasuratoare.out");
init();
fi >> n;
for (int i = 1; i <= n; i++)
fi >> AUX[i].x >> AUX[i].y,
process(AUX[i].x, AUX[i].y);
for (int i = 1; i <= n; i++)
if (!checkIfInside(AUX[i].x, AUX[i].y))
{
s++;
P[s].x = AUX[i].x, P[s].y = AUX[i].y;
}
sort(P+1, P+s+1, cmp);
st[1] = 1;
st[2] = 2;
viz[1] = viz[2] = true;
stSize = 2;
for (int i = 3; i <= n; i++)
{
while (stSize > 1 && det(P[st[stSize-1]], P[st[stSize]], P[i]) > E)
viz[st[stSize--]] = false;
st[++stSize] = i;
viz[i] = true;
}
for (int i = n; i > 0; i--)
{
if (viz[i])
continue;
while (stSize > 1 && det(P[st[stSize-1]], P[st[stSize]], P[i]) > E)
st[stSize--] = false;
st[++stSize] = i;
}
fo << stSize << "\n";
fo << fixed;
fo << setprecision(6) << P[st[1]].x << " " << P[st[1]].y << "\n";
for (int i = stSize; i > 1; i--)
fo << setprecision(6) << P[st[i]].x << " " << P[st[i]].y << "\n";
fi.close();
fo.close();
return 0;
}