Pagini recente » Cod sursa (job #2867667) | Cod sursa (job #1253952) | Cod sursa (job #316725) | Cod sursa (job #2373668) | Cod sursa (job #1189374)
#include <fstream>
#include <algorithm>
#include <vector>
#include <stack>
#include <iomanip>
using namespace std;
#define IN "infasuratoare.in"
#define OU "infasuratoare.out"
#define x first
#define y second
ifstream is (IN);
ofstream os (OU);
int N, H = 2;
pair <double, double> S[120005], V[120005];
pair <double, double> P, M(1000000000, 1000000000);
inline double CMP( const pair<double, double>& A, const pair<double, double>& B );
double CROSS(pair<double, double>& A, pair<double, double>& B, pair<double, double>& C);
int main()
{
///*** READ ***///
is >> N;
int pos;
for (int i = 1; i <= N; ++i)
{
is >> P.x >> P.y;
if (P < M)
M = P, pos = i;
V[i] = P;
}
///*** SORT ***///
swap (V[1], V[pos]);
sort (V+2, V+N+1, CMP);
///*** Convex Hull ***///
S[1] = V[1];
S[2] = V[2];
for (int i = 3; i <= N; ++i)
{
while (H >= 2 && CROSS(S[H-1], S[H], V[i]) < 0)
--H;
S[++H] = V[i];
}
os << fixed;
os << H << '\n';
for (int i = 1; i <= H; ++i)
os << setprecision(9) << S[i].x << ' ' << S[i].y << '\n';
is.close();
os.close();
}
double CROSS(pair<double, double>& A, pair<double, double>& B, pair<double, double>& C){
return (B.x - A.x) * (C.y - A.y) - (B.y - A.y) * (C.x - A.x);
};
inline double CMP( const pair<double, double>& A, const pair<double, double>& B ){
return (A.x - M.x) * (B.y - M.y) > (B.x - M.x) * (A.y - M.y);
}