Pagini recente » Cod sursa (job #2754673) | Cod sursa (job #1348688) | Cod sursa (job #545261) | Cod sursa (job #1693654) | Cod sursa (job #2381046)
#include <fstream>
#include <algorithm>
#include <iomanip>
using namespace std;
ifstream fin("infasuratoare.in");
ofstream fout("infasuratoare.out");
const int NMax = 120000, oo = 2e9;
int N, K, p;
struct pct{double x, y;} V[NMax + 5], S[NMax + 5];
int Det(pct A, pct B, pct C) {return (A.x * B.y + B.x * C.y + C.x * A.y - B.x * A.y - C.x * B.y - A.x * C.y);}
inline bool compare(pct A, pct B) {return Det(V[1], A, B) < 0;}
int main()
{
fin >> N; V[0] = {oo, oo}, p = 0;
for(int i = 1; i <= N; i++)
{
fin >> V[i].x >> V[i].y;
if(V[i].y < V[p].y || (V[i].y == V[p].y && V[i].x < V[p].x)) p = i;
}
swap(V[p], V[1]); sort(V + 2, V + N + 1, compare); S[++K] = V[1], S[++K] = V[2];
for(int i = 3; i <= N; i++)
{
while(K > 1 && Det(S[K], S[K - 1], V[i]) <= 0) K--;
S[++K] = V[i];
}
fout << K << '\n';
for(int i = K; i > 0; i--)
fout << fixed << setprecision(6) << S[i].x << " " << S[i].y << '\n';
fin.close();
fout.close();
return 0;
}