Pagini recente » Cod sursa (job #1239033) | Cod sursa (job #143937) | Cod sursa (job #1439881) | Cod sursa (job #2666491) | Cod sursa (job #2756501)
#include <iostream>
#include <iomanip>
#include <fstream>
#include <algorithm>
#include <cmath>
std::ifstream fin("infasuratoare.in");
std::ofstream fout("infasuratoare.out");
const double eps = 1.0e-14;
const double INF = 1e9;
const int NMAX = 120000;
struct POINT
{
double x, y;
};
POINT P[NMAX + 5], LL;
int h[NMAX + 5];
double cp(const POINT& P1, const POINT& P2, const POINT& P3)
{
return (P2.x - P1.x) * (P3.y - P2.y) - (P2.y - P1.y) * (P3.x - P2.x);
}
int ccw(const POINT& P1, const POINT& P2, const POINT& P3)
{
double crossprod = cp(P1, P2, P3);
if (fabs(crossprod) < eps)
return 0;
if (crossprod >= eps)
return 1;
return -1;
}
bool cmp(POINT& P1, POINT& P2)
{
return ccw(LL, P1, P2) > 0;
}
double arie_poligon(int n)
{
double aria;//aria = 0.5 * abs(suma de la i = 0 pana la n - 1 din det(xi xi+1 // yi yi+1))
int i;
P[n] = P[0];
aria = 0;
for (i = 0; i < n; ++i)
aria = P[i].x * P[i + 1].y - P[i + 1].x * P[i].y;
aria = 0.5 * fabs(aria);
return aria;
}
using namespace std;
int main()
{
int n, i, top;
double a, b;
fout << fixed;
fin >> n >> a >> b;
P[0].x = a;
P[0].y = b;
for (i = 1; i < n; ++i)
{
fin >> a >> b;
P[i].x = a;
P[i].y = b;
if (P[i].y - P[0].y <= -eps || ((fabs(P[i].y - P[0].y) < eps) && (P[i].x - P[0].x <= -eps)))
swap(P[i], P[0]);
}
LL = P[0];
P[n] = P[0];
h[0] = 0;
h[1] = 1;
sort(P + 1, P + n, cmp);
top = 1; i = 2;
while (i <= n)
{
if (ccw(P[h[top - 1]], P[h[top]], P[i]) > 0)
{
h[++top] = i;
++i;
}
else
{
--top;
}
}
fout << top << '\n';
for (i = 0; i < top; ++i)
fout << setprecision(6) << P[h[i]].x << ' ' << setprecision(6) << P[h[i]].y << '\n';
return 0;
}