Pagini recente » Cod sursa (job #655738) | Cod sursa (job #1602839) | Cod sursa (job #2697238) | Cod sursa (job #1585861) | Cod sursa (job #2753937)
#include <fstream>
#include <algorithm>
#include <cmath>
#include <iomanip>
const double eps = 1.0e-14;
const int NMAX = 120000;
struct POINT
{
double x, y;
};
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)
{
/// 1 ccw 0 coliniar -1 cw
double c = cp (p1, p2, p3);
if (fabs(c) < eps)
return 0;
if (c >= eps)
return 1;
return -1;
}
POINT P[NMAX+5];
POINT LL;
int h[NMAX+5];
bool cmp (POINT p1, POINT p2)
{
return (ccw(LL, p1, p2) > 0);
}
using namespace std;
ifstream cin ("infasuratoare.in");
ofstream cout ("infasuratoare.out");
int main()
{
int n, i, top;
cin >> n;
cin >> P[0].x >> P[0].y;
for (i=1; i<n; i++)
{
cin >> P[i].x >> P[i].y;
if (P[i].y - P[0].y <= -eps || fabs(P[i].y - P[0].y) < eps and P[i].x - P[0].x <= -eps)
swap (P[0], P[i]);
}
LL = P[0];
sort (P + 1, P + n, cmp);
h[0] = 0;
h[1] = 1;
top = 1;
P[n] = P[0];
i=2;
while (i <= n)
{
if (ccw(P[h[top-1]], P[h[top]], P[i]) > 0)
{
h[++top] = i;
i++;
}
else
top--;
}
// for (i=0; i<top; i++)
// cout << h[i] << " ";
//
// cout << "\n";
cout << top << "\n";
for (i=0; i<top; i++)
cout << fixed << setprecision(6) << P[h[i]].x << " " << P[h[i]].y << "\n";
return 0;
}