Pagini recente » Cod sursa (job #2517527) | Cod sursa (job #1700608) | Cod sursa (job #145208) | Cod sursa (job #445863) | Cod sursa (job #2379483)
#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;
struct pct{double x, y;} V[NMax + 5], O, S[NMax + 5];
inline bool compare(pct A, pct B)
{
return (A.y - O.y) * (B.x - O.x) < (A.x - O.x) * (B.y - O.y);
}
double 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);
}
int main()
{
fin >> N; O = {oo, oo};
for(int i = 1; i <= N; i++)
{
fin >> V[i].x >> V[i].y;
if(V[i].y < O.y)
O = V[i];
else if(V[i].y == O.y)
O.x = min(O.x, V[i].x);
}
sort(V + 1, 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 = 1; i <= K; i++)
fout << fixed << setprecision(6) << S[i].x << " " << S[i].y << '\n';
fin.close();
fout.close();
return 0;
}