Pagini recente » Cod sursa (job #2316303) | Cod sursa (job #202935) | Rating Popa Andrei (andreipopa97) | Cod sursa (job #3132866) | Cod sursa (job #728680)
Cod sursa(job #728680)
#include <fstream>
#include <vector>
#include <algorithm>
#include <iomanip>
#define DIM 120100
using namespace std;
int n;
pair<double, double> P[DIM];
int St[DIM];
bool s[DIM];
int pas, k, i;
void Read();
void Hill();
void GasestePunct();
int Semn(int, int, int);
bool Calc(pair<double, double>, pair<double, double>);
void Write();
int main()
{
Read();
Hill();
Write();
return 0;
}
void Read()
{
ifstream fin("infasuratoare.in");
fin >> n;
for (int i = 1; i <= n; ++i)
fin >> P[i].first >> P[i].second;
fin.close();
}
void Hill()
{
sort(P + 1, P + n + 1);
s[2] = 1;
St[1] = 1; St[2] = 2;
k = 2; // varful stivei - punem punctele 0 si 1 in stiva
i = 2;
pas = 1;
while (i > 1)
{
GasestePunct();
if (!i) return;
while (k > 1 && Semn(St[k-1], St[k], i) == -1)
{
s[St[k]] = 0;
k--;
}
St[++k] = i;
s[i] = 1;
}
}
void GasestePunct()
{
while (s[i])
{
i += pas;
if (i == n) pas = -1;
}
}
int Semn(int A, int B, int C)
{
double aa = P[A].second - P[B].second;
double bb = P[B].first - P[B].first;
double cc = P[A].first * P[B].second - P[B].first * P[A].second;
double x = P[C].first;
double y = P[C].second;
if ((aa * x + bb * y + cc) < 0) return -1;
return 1;
}
bool Calc(pair<double, double> A, pair<double, double> B)
{
return A.second < B.second || (A.second == B.second && A.first < B.first);
}
void Write()
{
ofstream fout("infasuratoare.out");
fout << k-1 << '\n';
for (int i = 1; i <= k; ++i)
fout << fixed << setprecision(12) << P[St[i]].first << ' '
<< fixed << setprecision(12) << P[St[i]].second << '\n';
fout.close();
}