Pagini recente » Cod sursa (job #1991820) | Cod sursa (job #1578243) | Cod sursa (job #535403) | Cod sursa (job #2698465) | Cod sursa (job #1411186)
#include <bits/stdc++.h>
using namespace std;
#define Point pair<double,double>
#define x first
#define y second
const int Nmax = 120000;
/**
< 0 for counter-clockwise (trigonometric)
= 0 for collinear
> 0 for clockwise (anti-trigonometric)
**/
double CCW(Point A, Point B, Point P)
{
return (P.x - A.x) * (B.y - A.y) - (P.y - A.y) * (B.x - A.x);
}
Point points[Nmax];
Point sol[Nmax];
void convexHull(Point points[], int N, Point hull[], int &sizeHull)
{
int U[Nmax], L[Nmax];
int dimU = 0, dimL = 0;
sizeHull = 0;
for (int i = 0; i < N; ++i)
{
while (dimU >= 2 && CCW(points[U[dimU - 2]], points[U[dimU - 1]], points[i]) >= 0)
dimU--;
U[dimU++] = i;
}
for (int i = N - 1; i >= 0; --i)
{
while (dimL >= 2 && CCW(points[L[dimL - 2]], points[L[dimL - 1]], points[i]) >= 0)
dimL--;
L[dimL++] = i;
}
dimU--;
dimL--;
for (int i = 0; i < dimU; ++i)
hull[sizeHull++] = points[U[i]];
for (int i = 0; i < dimL; ++i)
hull[sizeHull++] = points[L[i]];
}
int main()
{
ifstream in("infasuratoare.in");
ofstream out("infasuratoare.out");
int N, dim = 0;
in >> N;
for (int i = 0; i < N; ++i)
in >> points[i].x >> points[i].y;
convexHull(points, N, sol, dim);
out << dim << "\n";
for (int i = 0; i < dim; ++i)
{
out << fixed << setprecision(10);
out << sol[i].x << " " << sol[i].y << "\n";
}
return 0;
}