Pagini recente » Cod sursa (job #2532128) | Cod sursa (job #1674650) | Cod sursa (job #2337020) | Cod sursa (job #1422339) | Cod sursa (job #1189243)
#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 <float, float> S[120005], V[120005];
pair <float, float> P, M(1000000000, 1000000000);
inline float CMP( const pair<float, float>& A, const pair<float, float>& B );
double CROSS(pair<float, float>& A, pair<float, float>& B, pair<float, float>& 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 << H << '\n';
for (int i = 2; i <= H; ++i)
os << fixed << S[i].x << ' ' << S[i].y << '\n';
os << fixed << S[1].x << ' ' << S[1].y << '\n';
is.close();
os.close();
}
double CROSS(pair<float, float>& A, pair<float, float>& B, pair<float, float>& C){
return (B.x - A.x) * (C.y - A.y) - (B.y - A.y) * (C.x - A.x);
};
inline float CMP( const pair<float, float>& A, const pair<float, float>& B ){
return (A.x - M.x) * (B.y - M.y) > (B.x - M.x) * (A.y - M.y);
}