Pagini recente » Cod sursa (job #983067) | Cod sursa (job #1944240) | Cod sursa (job #1021415) | Cod sursa (job #496997) | Cod sursa (job #580356)
Cod sursa(job #580356)
// Alg. HILL
#include <fstream>
#include <algorithm>
#include <vector>
#include <iomanip>
#define DIM 121000
using namespace std;
int n, k;
pair<double ,double> P[DIM];
int pas, i;
int S[DIM]; // stiva
bool s[DIM];
void Read();
void Write();
void Hill();
void GasestePunct();
int Semn(pair<double, double>, pair<double, double>,pair<double, double>);
bool Calc(pair<double, double>, pair<double, double>);
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, Calc); // sortam dupa abscisa (ordonata in caz de egalitate)
s[2] = true;
S[1] = 1; S[2] = 2; // punem in stiva primele 2 puncte
pas = 1;
i = 2; // pozitia in sirul curent
k = 2; // varful stivei
while (i > 1)
{
GasestePunct(); // i indica punct neselectat
if (!i) break;
while ((k > 1) && Semn(P[S[k-1]], P[S[k]], P[i]) == -1) // == unghiul dintre [A,B] si P[i] este > 180
{
s[S[k]] = 0;
k--;
}
k++;
s[i] = 1;
S[k] = i;
}
}
void GasestePunct()
{
while (s[i])
{
i += pas;
if (i == n) pas = -1;
}
}
int Semn(pair<double, double> A , pair<double, double> B ,pair<double, double> C)
{
double aa = A.second - B.second;
double bb = B.first - A.first;
double cc = A.first * B.second - A.second * B.first;
if ((aa * C.first + bb * C.second + 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(6) << P[S[i]].first;
fout << ' ' << fixed << setprecision(6) << P[S[i]].second << '\n';
}
fout.close();
}