Pagini recente » Cod sursa (job #986874) | Cod sursa (job #726866) | Cod sursa (job #188665) | Istoria paginii utilizator/a_person_135 | Cod sursa (job #547239)
Cod sursa(job #547239)
#include <fstream>
#include <algorithm>
#include <iomanip>
#include <cmath>
#define DIM 220000
#define eps 0.000001
using namespace std;
ofstream fout("mosia.out");
struct Punct {
double x;
double y;
}a[DIM];
int n, vf, il, pas;
int p[DIM]; // stiva
bool s[DIM];
void Read();
void Write();
void Hill();
void GasestePunct();
bool Calc(Punct A, Punct B);
int IntoarceDreapta(Punct A, Punct B, Punct C);
int main()
{
Read();
sort(a + 1, a + n + 1, Calc);
Hill();
Write();
return 0;
}
void Read()
{
ifstream fin("infasuratoare.in");
fin >> n;
for (int i = 1; i <= n; ++i)
fin >> a[i].x >> a[i].y;
fin.close();
}
void Hill()
{
p[++vf] = 1;
p[++vf] = 2;
s[2] = 1;
il = 2; // contor pt puncte
pas = 1;
while ( il > 1 )
{
GasestePunct();
if ( il == 0 ) break;
while (vf > 1 && IntoarceDreapta(a[p[vf]], a[p[vf-1]], a[il]))
{
s[vf] = 0;
vf--;
}
p[++vf] = il;
s[il] = 1;
}
}
void GasestePunct()
{
while ( s[il] )
{
il += pas;
if (il == n) pas = -1; //daca am ajuns in elementul cu ordonata cea mai mare, ne intoarcem
}
}
int IntoarceDreapta(Punct A, Punct B, Punct C)
{
double x1 = A.x;
double y1 = A.y;
double x2 = B.x;
double y2 = B.y;
double x3 = C.x;
double y3 = C.y;
if ((x2-x1) * (y3-y1) - (x3-x1) * (y2-y1) <= 0) return 1;
return 0;
}
void Write()
{
ofstream fout("infasuratoare.out");
fout << vf << '\n';
for (int i = 1; i <= vf; ++i)
fout << fixed << setprecision(6) << a[p[i]].x << ' ' << fixed << setprecision(6) << a[p[i]].y << '\n';
fout.close();
}
bool Calc(Punct A, Punct B)
{
return (A.y < B.y || (A.y == B.y && A.x < B.x));
}