Pagini recente » Cod sursa (job #394288) | Cod sursa (job #1939556) | Cod sursa (job #2556626) | Cod sursa (job #272008) | Cod sursa (job #580346)
Cod sursa(job #580346)
/* ACOPERIREA POLIGONALA (ALG. LUI HILL)
Se sorteaza punctele in functie de ordonata, iar daca au ordonate egale,
in functie de abscisa. La fiecare pas se alege cate un punct neselectat, care
sa formeze cu ultimele 2 puncte puse in stiva un unghi mai mic de 180 grade.
(avem in vedere faptul ca se formeaza un poligon convex care are masura unui
unghi interior mai mic de 180 grade).
In stiva se vor afla punctele ordonate in sens trigonometric, incepand cu
punctul care are ordonata cea mai mica si abscisa cea mai mica si terminand
cu acelasi punct.
*/
#include <fstream>
#include <algorithm>
#include <iomanip>
#define maxn 110001
using namespace std;
struct punct {
double x;
double y;
} p[maxn], aux;
ofstream fout("infasuratoare.out");
int n;
int sel[maxn]; // sel[i] = 1, daca punctul i a fost selectat
int st[maxn]; // stiva folosita
int i, k, pas;
double aa, bb, cc;
void Read();
void Hill();
void QuickSort(int lf, int rt);
void Modifica();
void GasestePunct();
int Semn(punct A, punct B, punct C);
void Coeficienti(punct A, punct B);
void Write();
int main()
{
Read();
Hill();
Write();
return 0;
}
void Read()
{
ifstream fin("infasuratoare.in");
fin >> n;
for ( i = 1; i <= n; i++ )
fin >> p[i].x >> p[i].y;
fin.close();
}
void Hill()
{
QuickSort(1, n); // reetichetare a nodurilor
st[1] = 1;
st[2] = 2;
sel[2] = 1;
k = 2; // varful stivei
i = 2; // contor pt puncte
pas = 1;
while ( i > 1 )
{
GasestePunct();
if ( i == 0 ) break;
while ( ( k > 1 ) && ( Semn(p[st[k-1]], p[st[k]], p[i]) == -1 ) )
{
sel[st[k]] = 0;
k--;
}
k++;
st[k] = i;
sel[i] = 1;
}
} // a
void GasestePunct()
{
while ( sel[i] )
{
i += pas;
if (i == n) pas = -1; //daca am ajuns in elementul cu ordonata cea mai mare, ne intoarcem
}
}
void QuickSort(int lf, int rt)
{
if ( lf < rt )
{
int i = lf - 1, j = rt + 1;
do
{
do
{
i++;
} while ( p[i].y < p[lf].y || ( p[i].y == p[lf].y && p[i].x < p[lf].x ) );
do
{
j--;
} while ( p[j].y > p[lf].y || ( p[j].y == p[lf].y && p[j].x > p[lf].x ) );
if ( i < j )
{
aux = p[i];
p[i] = p[j];
p[j] = aux;
}
} while ( i < j );
QuickSort(lf, j);
QuickSort(j + 1, rt);
}
}
int Semn(punct A, punct B, punct C)
{
Coeficienti(A, B); // calculeaza coeficientii dreptei care trece prin punctele A si B
if ( aa * C.x + bb * C.y + cc < 0 )
return -1; // datorita lui C iese B din stiva
return 1;
}
void Coeficienti(punct A, punct B)
{
aa = A.y - B.y;
bb = B.x - A.x;
cc = A.x * B.y - B.x * A.y;
}
void Write()
{
int i = 0;
fout << k-1 << '\n';
for ( i = 1; i < k; i++ )
fout << fixed << setprecision(6) << p[st[i]].x << " " << fixed << setprecision(6) << p[st[i]].y << "\n";
fout.close();
}